Graphs go beyond hierarchies. They model the chaos of the real world2from social networks to shipping routes2using two simple primitives: Vertices and Edges.

Vertices: O(V)

Edges: O(E)

network_lab_v1.0

Graph Ontology

Vertex (Node)

The 'Noun' of the graph. Represents an entity like a user, a city, or a router.

Edge (Arc)

The 'Verb'. Represents the relationship or connection between two vertices.

Degree

Connectivity count. In directed graphs, this splits into In-degree and Out-degree.

The "Tree" Clarification

"Every Tree is a Graph, but not every Graph is a Tree."

TREE RULES

2 Connected
2 Acyclic (No Cycles)
2 Rooted (Usually)

GRAPH RULES

2 Disjoint sets allowed
2 Cycles allowed
2 Any starting point

Connection Types

Undirected: Edges are mutual. Relationship exists in both directions simultaneously.

Logic to Hardware

How do we store this mess in a computer? We have two competing standards: one for Fast Access and one for Space Efficiency.

Select Matrix or List to see how this specific network structure maps to memory.

The Engineering Trade-off

Operation	Adjacency List	Adjacency Matrix
Space Complexity	O(V + E)	O(V2)
Checking Edge (u,v)	O(Degree)	O(1)
Finding Neighbors	O(Degree)	O(V)
Memory Profile	Ptr Chasing (Cache Misses)	Contiguous (Cache Friendly)

Interviewer's Secret: Edge Cases

When asked to store a graph with billions of nodes (like Facebook's social graph), always choose an Adjacency List. Why? Facebook is a **Sparse Graph**. Most people don't have billions of friends; the matrix would be 99.9999% zeros2a catastrophic waste of memory.

Industry Standards

The blueprint for a production-ready Graph class using an Adjacency List.

optimal_implementation.js

Pseudocode

1// Optimal Adjacency List (using a Hash Map)
2class Graph {
3  constructor() {
4    this.adjList = new Map();
5  }
6 
7  addVertex(v) {
8    if (!this.adjList.has(v)) {
9      this.adjList.set(v, []);
10    }
11  }
12 
13  addEdge(v, w, isDirected = false) {
14    this.addVertex(v);
15    this.addVertex(w);
16    this.adjList.get(v).push(w);
17    if (!isDirected) {
18      this.adjList.get(w).push(v);
19    }
20  }
21 
22  getNeighbors(v) {
23    return this.adjList.get(v) || [];
24  }
25}

Key Patterns

2Use Map/Object for vertex lookup to handle strings/objects instead of just integers.
2Use Sets instead of Arrays in the Adjacency List if you need O(1) edge removal.
2Consider Edge Lists (simple array of pairs) for Kruskal's algorithm or Bellman-Ford.

Ready to Traverse?

Now that we can store graphs, let's learn how to walk through them with BFS/DFS.

The Engineering Trade-off

Operation	Adjacency List	Adjacency Matrix
Space Complexity	O(V + E)	O(V2)
Checking Edge (u,v)	O(Degree)	O(1)
Finding Neighbors	O(Degree)	O(V)
Memory Profile	Ptr Chasing (Cache Misses)	Contiguous (Cache Friendly)

Interviewer's Secret: Edge Cases

1// Optimal Adjacency List (using a Hash Map) 2class Graph { 3 constructor() { 4 this.adjList = new Map(); 5 } 6 7 addVertex(v) { 8 if (!this.adjList.has(v)) { 9 this.adjList.set(v, []); 10 } 11 } 12 13 addEdge(v, w, isDirected = false) { 14 this.addVertex(v); 15 this.addVertex(w); 16 this.adjList.get(v).push(w); 17 if (!isDirected) { 18 this.adjList.get(w).push(v); 19 } 20 } 21 22 getNeighbors(v) { 23 return this.adjList.get(v) || []; 24 } 25}

Course Navigation

Module Progress

Module Stats

The Science of Connected Data

Graph Ontology

Vertex (Node)

Edge (Arc)

Degree

The "Tree" Clarification

Connection Types

Logic to Hardware

The Engineering Trade-off

Interviewer's Secret: Edge Cases

Industry Standards

Key Patterns

Ready to Traverse?

Course Navigation

Module Progress

Module Stats

The Science of Connected Data

Graph Ontology

Vertex (Node)

Edge (Arc)

Degree

The "Tree" Clarification

Connection Types

Logic to Hardware

The Engineering Trade-off

Interviewer's Secret: Edge Cases

Industry Standards

Key Patterns

Ready to Traverse?

The Science of
Connected Data

The Science of
Connected Data