Graph Representation & Traversals

Q: What is the time and space complexity of BFS and DFS?

BFS and DFS both have time complexity O(V+E) with adjacency list representation (O(V^2) with adjacency matrix). Space: BFS uses O(V) for the queue plus O(V) visited array = O(V). DFS uses O(V) for the stack (recursion) plus O(V) visited array = O(V). Both visit every vertex and edge exactly once.

Q: When should you use adjacency matrix vs adjacency list?

Adjacency matrix: O(V^2) space, O(1) edge lookup. Use for dense graphs (E close to V^2) or when you frequently check if an edge exists. Adjacency list: O(V+E) space, O(degree) edge lookup. Use for sparse graphs (E << V^2) or when you frequently iterate over neighbours. Most GATE graph problems assume adjacency list for time complexity analysis.

Q: What is topological sorting and when does it exist?

Topological sort is a linear ordering of vertices such that for every directed edge (u,v), u comes before v. It exists if and only if the graph is a Directed Acyclic Graph (DAG) - no cycles. Algorithm: DFS-based (add to stack on finish) or Kahn's BFS-based (use in-degree, repeatedly remove nodes with in-degree 0). Time: O(V+E).

Q: How does DFS detect a cycle in a directed graph?

DFS maintains three states for each vertex: WHITE (unvisited), GRAY (in current DFS path/recursion stack), BLACK (finished). A back edge (edge to a GRAY ancestor) indicates a cycle. In an undirected graph, any edge to an already-visited vertex (other than the parent) is a back edge indicating a cycle.

Adjacency matrix vs list, BFS, DFS, topological sort, cycle detection — the graph data structure foundation that underpins the Algorithms cluster too.

Last updated: April 2026 | GATE CS 2024–2026 syllabus

Key Takeaways

Graph G = (V, E). Directed (digraph) or undirected. Weighted or unweighted.
Adjacency matrix: O(V²) space, O(1) edge query. Best for dense graphs.
Adjacency list: O(V+E) space, O(degree) neighbour iteration. Best for sparse graphs.
BFS: queue, visits level by level. Single-source shortest path in unweighted graph.
DFS: stack (or recursion), explores depth-first. Detects cycles, finds SCCs, topological sort.
Both BFS and DFS: O(V+E) time with adjacency list, O(V²) with matrix.
Topological sort: exists iff graph is a DAG. DFS-based or Kahn’s BFS-based. O(V+E).

1. Graph Definitions

Term	Definition
Degree (undirected)	Number of edges incident to vertex v
In-degree/Out-degree	Directed graph: edges coming in / going out
Path	Sequence of vertices connected by edges
Simple path	Path with no repeated vertices
Cycle	Path where start = end; at least one edge
DAG	Directed Acyclic Graph; no directed cycles
Connected graph	Undirected: path exists between every pair
Strongly connected	Directed: path in both directions between every pair
Tree	Connected acyclic undirected graph. n vertices, n−1 edges.

Handshaking lemma: ∑_v degree(v) = 2|E| (undirected)
∑ in-degree = ∑ out-degree = |E| (directed)

2. Representations: Matrix vs List

Property	Adjacency Matrix	Adjacency List
Space	O(V²)	O(V + E)
Check if edge (u,v) exists	O(1)	O(degree(u))
Iterate all neighbours of u	O(V)	O(degree(u))
Add edge	O(1)	O(1)
BFS / DFS time	O(V²)	O(V + E)
Best for	Dense graphs (E ≈ V²)	Sparse graphs (E << V²)

Undirected graph matrix: Symmetric (A[i][j] = A[j][i]).
Directed graph matrix: Not necessarily symmetric.
Weighted graph: Matrix stores weights; list stores (neighbour, weight) pairs.

3. Breadth-First Search (BFS)

Algorithm (source s):
1. Mark s visited, enqueue s.
2. While queue not empty: dequeue u; for each unvisited neighbour v of u: mark v visited, enqueue v.

Time: O(V+E) with adjacency list
Space: O(V) for queue and visited array

BFS Applications

Unweighted shortest path: BFS gives the shortest path (in terms of number of edges) from source s to all reachable vertices.
Bipartite check: 2-colour the graph during BFS. If a same-colour conflict arises, not bipartite.
Level-order tree traversal.
Connected components (run BFS from each unvisited vertex).

BFS tree: edges used by BFS form a spanning tree. Distance d[v] = shortest edge-count path from s to v.

4. Depth-First Search (DFS)

Recursive DFS(u):
1. Mark u visited; record discovery time d[u].
2. For each neighbour v of u: if unvisited, DFS(v).
3. Record finish time f[u].

Time: O(V+E) Space: O(V) recursion stack

DFS Edge Classification (Directed Graph)

Edge Type	Condition	Significance
Tree edge	v discovered via u	Builds DFS forest
Back edge	v is ancestor of u (GRAY)	Indicates cycle
Forward edge	v is descendant, already finished	Directed graphs only
Cross edge	v in different DFS tree	Directed graphs only

Undirected graph: Only tree edges and back edges exist. A back edge = cycle.

DFS Applications

Cycle detection (back edge in directed; any revisited non-parent in undirected)
Topological sort (finish times in reverse)
Strongly connected components (Kosaraju’s / Tarjan’s)
Articulation points and bridges

5. Cycle Detection

Directed Graph

DFS colour states: WHITE (unvisited), GRAY (in stack), BLACK (finished).
Cycle exists ⇔ a back edge found (edge from GRAY to GRAY ancestor).

Undirected Graph

DFS: cycle exists if any vertex has an already-visited neighbour other than its DFS parent.
Alternatively: Union-Find (Disjoint Set Union) — if adding edge (u,v) and find(u)==find(v), cycle.

6. Topological Sort

Linear ordering of vertices where for every edge (u,v), u appears before v. Only for DAGs.

Method 1: DFS-based

Run DFS; push each vertex to stack when finished (BLACK).
Pop stack → topological order.
Time: O(V+E)

Method 2: Kahn’s Algorithm (BFS-based)

1. Compute in-degree of all vertices.
2. Enqueue all vertices with in-degree 0.
3. While queue not empty: dequeue u, output u; for each neighbour v, decrement in-degree[v]; if in-degree[v]==0, enqueue v.
4. If output count < V: cycle exists (not a DAG).
Time: O(V+E)

Kahn’s advantage: Naturally detects if the graph is a DAG (output count == V iff no cycle).

7. Connected Components

Undirected Graph — Connected Components

Run BFS or DFS from each unvisited vertex. Each run finds one connected component. Time: O(V+E).

Directed Graph — Strongly Connected Components (SCC)

Kosaraju’s algorithm:
1. Run DFS on original graph G; push vertices to stack by finish time.
2. Transpose G (reverse all edges) to get G^T.
3. Run DFS on G^T in order of decreasing finish time (pop from stack).
Each DFS tree in step 3 = one SCC. Time: O(V+E).

8. GATE CS Solved Examples

Example 1 — BFS/DFS complexity (GATE CS 2018)

Q: A connected graph has V=1000 vertices and E=500,000 edges. What is the time complexity of BFS using (a) adjacency matrix, (b) adjacency list?

(a) Adjacency matrix: O(V²) = O(10⁶)
(b) Adjacency list: O(V+E) = O(1000 + 500000) = O(501000) ≈ O(5×10⁵)
Adjacency list is 2× faster for this dense graph. For very dense graphs, both are O(V²).

Example 2 — Topological sort (GATE CS 2021)

Q: DAG with edges: 1→2, 1→3, 2→4, 3→4, 4→5. List all valid topological orderings.

In-degrees: 1=0, 2=1, 3=1, 4=2, 5=1. Start with vertex 1 (only in-degree 0).

After removing 1: in-degrees 2=0, 3=0. Both can go next.

Valid orderings: 1,2,3,4,5 and 1,3,2,4,5 (two valid orderings since 2 and 3 are independent).

Example 3 — DFS tree edges (GATE CS 2019)

Q: In DFS of an undirected graph, what kind of edges can appear? How many back edges indicate a cycle?

Undirected DFS: only tree edges and back edges. Forward and cross edges do NOT exist in undirected DFS.
Any back edge indicates a cycle. Exactly one back edge per cycle in a DFS tree.

9. Common Mistakes

Mistake 1 — BFS gives shortest path in weighted graphs

BFS shortest path is valid only for unweighted graphs (or graphs with equal weights). For weighted graphs, use Dijkstra’s (non-negative) or Bellman-Ford (negative weights).

Mistake 2 — DFS time with adjacency matrix

DFS with adjacency matrix is O(V²) not O(V+E) because checking all neighbours of a vertex takes O(V) (scan the entire row). With adjacency list, each vertex’s neighbours are listed directly.

Mistake 3 — Topological sort on graphs with cycles

Topological sort is only defined for DAGs. If the graph has a cycle, no valid topological ordering exists. Kahn’s algorithm detects this: if output size < V after processing, a cycle exists.

Mistake 4 — Confusing connected and strongly connected

Connected applies to undirected graphs (path between every pair). Strongly connected applies to directed graphs (path in both directions). A directed graph can be connected (ignoring direction) but not strongly connected.

Mistake 5 — Forward/cross edges in undirected DFS

In undirected DFS, there are NO forward edges and NO cross edges — only tree edges and back edges. Forward and cross edges only appear in directed graph DFS.

10. FAQ

What is the time and space complexity of BFS and DFS?

Both: O(V+E) time with adjacency list, O(V²) with matrix. Space O(V) for queue/stack and visited array.

When should you use adjacency matrix vs adjacency list?

Matrix: dense graphs, O(1) edge lookup needed. List: sparse graphs, O(V+E) traversal. Most GATE problems assume adjacency list.

What is topological sorting and when does it exist?

Linear order of vertices where every edge (u,v) has u before v. Exists iff graph is a DAG. Algorithm: DFS (reverse finish order) or Kahn’s (in-degree BFS). O(V+E).

How does DFS detect a cycle in a directed graph?

Track vertex states: WHITE/GRAY/BLACK. A back edge (to a GRAY vertex) indicates a cycle. In undirected graphs, any edge to a visited non-parent vertex is a back edge.

Graph Representation and Traversals – Data Structures | GATE CS