Graph Representations & Basic Algorithms
Adjacency matrix/list, BFS/DFS, topological sort, and Union-Find from a data structures perspective.
Key Points
- ·Adjacency matrix: O(V²) space, O(1) edge lookup, good for dense graphs
- ·Adjacency list: O(V+E) space, O(degree) edge lookup, good for sparse graphs
- ·BFS: level-order using queue; finds shortest path in unweighted graphs
- ·DFS: uses stack/recursion; produces DFS tree, discovery/finish times
- ·Topological sort: DFS-based (reverse finish order) or Kahn algorithm (BFS with in-degree)
- ·Union-Find (Disjoint Set Union): union by rank + path compression → nearly O(1) per op
Graphs — A Map of Connections
A graph is a collection of vertices (cities) connected by edges (roads). Facebook friends, Google Maps, the internet — all graphs.
Graph with 4 vertices:
1
/ \
2 3
\ /
4
Two ways to store this:
Adjacency Matrix — A Table of Connections
Make a V×V table. Put 1 if there's an edge between i and j, else 0.
Graph: 1-2, 1-3, 2-4, 3-4
1 2 3 4
1 [0, 1, 1, 0]
2 [1, 0, 0, 1]
3 [1, 0, 0, 1]
4 [0, 1, 1, 0]
Check if edge (2,4) exists: matrix[2][4] = 1. Takes O(1) — instant. Find all neighbors of vertex 2: scan row 2 — takes O(V). Space: V² cells, so O(V²). Wasteful if the graph is sparse (few edges).
Adjacency List — A List Per Vertex
Each vertex has a list of its neighbors:
1 → [2, 3]
2 → [1, 4]
3 → [1, 4]
4 → [2, 3]
Space: O(V + E) — only stores actual edges. Much better for sparse graphs. Check if edge (2,4) exists: scan list of 2 — O(degree(2)). Find all neighbors of 2: O(degree(2)).
Rule of thumb: Use adjacency list for most real problems. Use matrix only if the graph is dense (many edges, E ≈ V²) or you need O(1) edge lookup constantly.
BFS — Exploring Level by Level
BFS is like dropping a stone in water and watching the ripples expand level by level.
Use a queue. Start from source, visit all neighbors first, then neighbors' neighbors.
Graph: 1-2, 1-3, 2-4, 2-5, 3-6
BFS from vertex 1:
Queue: [1] Visited: {1}
Dequeue 1 → visit neighbors 2, 3
Queue: [2, 3] Visited: {1, 2, 3}
Dequeue 2 → visit neighbors 4, 5
Queue: [3, 4, 5] Visited: {1, 2, 3, 4, 5}
Dequeue 3 → visit neighbor 6
Queue: [4, 5, 6] Visited: {1, 2, 3, 4, 5, 6}
Dequeue 4, 5, 6 → no unvisited neighbors
Done.
BFS tree:
1
/ \
2 3
/ \ \
4 5 6
BFS gives the shortest path (minimum hops) from source to every reachable vertex in an unweighted graph.
dist[1]=0, dist[2]=1, dist[3]=1, dist[4]=2, dist[5]=2, dist[6]=2
Time: O(V + E)
DFS — Exploring One Path as Far as Possible
DFS is like a maze explorer who always goes as deep as possible before backtracking.
Use a stack (or recursion). Mark discovery time d[v] and finish time f[v].
DFS from vertex 1 (same graph):
Visit 1 (d=1) → go to 2 (d=2) → go to 4 (d=3) → dead end
Backtrack to 2, go to 5 (d=4) → dead end, backtrack
Finish 2 (f=5), backtrack to 1
Go to 3 (d=6) → go to 6 (d=7) → dead end
Finish 6 (f=8), finish 3 (f=9), finish 1 (f=10)
Edge Types in Directed Graphs
| Edge type | What it means |
|---|---|
| Tree edge | Discovered a new vertex |
| Back edge | Leads to an ancestor → CYCLE detected! |
| Forward edge | Leads to a descendant already finished |
| Cross edge | Neither ancestor nor descendant |
In undirected graphs, only tree edges and back edges exist.
Topological Sort — Ordering Dependencies
Only for DAGs (Directed Acyclic Graphs). Think of it as ordering courses where some must be taken before others.
Method 1: Kahn Algorithm (BFS-based)
Step 1: Compute in-degree (number of incoming edges) for each vertex.
Step 2: Add all vertices with in-degree 0 to a queue.
Step 3: While queue is not empty:
- Dequeue vertex u, add to result
- For each neighbor v of u: decrease in-degree[v] by 1
- If in-degree[v] becomes 0: add v to queue
Step 4: If result has fewer than V vertices → cycle exists (not a DAG)
Example: A→C, B→C, C→D
In-degrees: A=0, B=0, C=2, D=1
Queue: [A, B]
Dequeue A → result: [A], decrease in-degree[C] to 1
Dequeue B → result: [A,B], decrease in-degree[C] to 0 → enqueue C
Dequeue C → result: [A,B,C], decrease in-degree[D] to 0 → enqueue D
Dequeue D → result: [A,B,C,D]
Valid topological order!
Union-Find — Grouping Connected Components
Imagine students in groups. Union-Find answers: "Are student A and B in the same group?" and "Merge group of A with group of B."
parent[i] = which group i belongs to (starts as itself)
find(x): follow parent pointers until root
union(x, y): make root of x's group point to root of y's group
Path compression: when you call find(x), make every node on the path point directly to root. Future finds are O(1).
Union by rank: always attach smaller tree under larger tree.
Together: nearly O(1) per operation (technically O(α(n)), inverse Ackermann — effectively constant).
Example: union(1,2), union(2,3), find(1)==find(3)?
After union(1,2): parent[1]=2
After union(2,3): parent[2]=3
find(1): 1→2→3 (root=3), with path compression: parent[1]=3
find(3): 3 (root=3)
find(1)==find(3)? Yes → same component.
Quick Check
Q1. In a graph with V=5 vertices and E=4 edges, which representation uses less space?
Answer: Adjacency list — uses O(V+E) = O(9) vs matrix O(V²) = O(25).
Q2. BFS from vertex 1 in graph 1-2, 1-3, 2-4, 3-4. What is the shortest path distance from 1 to 4?
Answer: 2 — path 1→2→4 or 1→3→4, both length 2.
Q3. Is a back edge in DFS a sign of a cycle?
Answer: Yes — a back edge connects a vertex to its ancestor, creating a cycle.
Key Formulas
- BFS/DFS time complexity: O(V + E)
- Adjacency matrix space: O(V²); Adjacency list space: O(V + E)
- DSU with path compression + union by rank: O(α(n)) per operation
GATE Exam Tips
- ★GATE gives a graph and asks to trace BFS/DFS — simulate step by step, level by level for BFS
- ★Topological sort exists iff graph is a DAG — Kahn algorithm detects cycle if output size < V
- ★Know both DFS and Kahn topological sort — GATE asks which approach was used
- ★BFS finds shortest path in unweighted graphs; for weighted graphs you need Dijkstra
Finished reading this topic?
Mark it complete to track your study progress.