Graph Algorithms
BFS, DFS, shortest paths, MST, SCC, topological sort — complete GATE CS coverage with complexity analysis.
Last updated: April 2026 | GATE CS 2024–2026 syllabus
Key Takeaways
- BFS: shortest path (unweighted), O(V+E). DFS: cycle detection, topo sort, SCC, O(V+E).
- Dijkstra: SSSP non-negative edges, O((V+E)log V). Bellman-Ford: negative edges, O(VE).
- Floyd-Warshall: all-pairs SP, O(V³). Johnson’s: all-pairs sparse, O(VE + V² log V).
- Kruskal: MST, O(E log E). Prim: MST dense, O(V²) or O(E log V) with heap.
- Topological sort: valid only for DAG. DFS-based or Kahn’s (BFS) both O(V+E).
- SCC: Kosaraju’s or Tarjan’s, both O(V+E).
- Max flow: Ford-Fulkerson O(E·maxflow), Edmonds-Karp O(VE²).
1. BFS & DFS
Data structure: Queue. Explores by levels (distance from source).
Time: O(V+E) adj. list, O(V²) adj. matrix
Finds: shortest path (unweighted), bipartiteness check, connected components.
BFS tree edges + cross edges only (no back edges in undirected).
DFS (Depth-First Search):
Data structure: Stack (or recursion). Explores as deep as possible first.
Time: O(V+E)
Finds: cycle detection, topological sort (reverse finish time), SCC, articulation points, bridges.
DFS edge classification: tree, back, forward, cross (directed); tree, back only (undirected).
| Property | BFS | DFS |
|---|---|---|
| Data structure | Queue | Stack / recursion |
| Shortest path | Yes (unweighted) | No |
| Cycle detection | Yes | Yes (via back edge) |
| Topological sort | Yes (Kahn’s) | Yes (reverse finish) |
| SCC | No | Yes (Kosaraju/Tarjan) |
2. Single-Source Shortest Paths
Greedy: extract min dist vertex, relax neighbours.
O((V+E) log V) binary heap O(E + V log V) Fibonacci heap
Bellman-Ford: Allows negative weights. Detects negative cycles.
Relax all E edges, V−1 times. V-th pass detects negative cycle.
Time: O(VE) Space: O(V)
DAG Shortest Path: Topological sort + single pass of relaxation = O(V+E).
Works with negative edges (no cycles in DAG).
When to use:
Non-negative: Dijkstra
Negative edges, no neg cycle: Bellman-Ford
DAG: topological sort + relax (O(V+E))
Unweighted: BFS
3. All-Pairs Shortest Paths
dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]) for each intermediate k.
Time: O(V³) Space: O(V²)
Works with negative edges. Detects neg cycle: dist[i][i]<0.
Johnson’s Algorithm:
Reweight edges to make all non-negative (Bellman-Ford from new source), then run Dijkstra from every vertex.
Time: O(VE + V² log V) with Fibonacci heap
Better than Floyd-Warshall for sparse graphs.
4. Minimum Spanning Trees
Kruskal’s: Sort edges by weight. Add if no cycle (Union-Find).
O(E log E) ≈ O(E log V)
Prim’s: Grow tree vertex by vertex. Pick minimum edge to non-tree vertex.
O(V²) with array O(E log V) with binary heap
Key properties:
Cut property: min weight edge crossing any cut is in MST.
Cycle property: max weight edge in any cycle is NOT in MST.
MST has exactly V−1 edges. Not unique if equal weights exist.
Second minimum spanning tree: remove one MST edge, find min replacement.
5. Topological Sort
DFS method: Run DFS; output vertices in reverse finish-time order.
Finish times are decreasing in topological order.
Kahn’s algorithm (BFS):
1. Compute in-degree of all vertices.
2. Enqueue all vertices with in-degree 0.
3. Process: dequeue u, output u, decrement in-degree of neighbours; enqueue if 0.
If output size < V: graph has a cycle (no valid topological order).
Both: O(V+E). Kahn’s also detects cycles.
6. Strongly Connected Components (SCC)
Kosaraju’s Algorithm (2-pass DFS):
Pass 1: DFS on original graph G; push vertices to stack in finish order.
Pass 2: Transpose G (reverse all edges). Pop from stack; DFS on GT.
Each DFS tree in pass 2 = one SCC.
Time: O(V+E)
Tarjan’s Algorithm (1-pass DFS):
Maintain discovery time and low-link value. Use stack.
When low[v]=disc[v]: pop stack to get SCC.
Time: O(V+E) Advantage: single pass.
7. Network Flow
Ford-Fulkerson: Find augmenting paths in residual graph, augment.
Time: O(E · max_flow) with DFS (not polynomial for irrational capacities)
Edmonds-Karp: Ford-Fulkerson with BFS for shortest augmenting path.
Time: O(VE²) — polynomial
Residual graph: For edge (u,v) with capacity c and flow f: forward edge c−f, backward edge f.
Cut: Partition (S,T) with s∈S, t∈T. Capacity = sum of forward edge capacities from S to T.
Bipartite matching: Max matching in bipartite graph = max flow (add source/sink with capacity 1 edges). O(VE).
8. Algorithm Summary
| Algorithm | Problem | Time | Constraint |
|---|---|---|---|
| BFS | SSSP (unweighted) | O(V+E) | — |
| Dijkstra (heap) | SSSP | O((V+E) log V) | Non-negative weights |
| Bellman-Ford | SSSP | O(VE) | No negative cycles |
| DAG SP | SSSP on DAG | O(V+E) | DAG only |
| Floyd-Warshall | All-pairs SP | O(V³) | No negative cycles |
| Johnson’s | All-pairs SP | O(VE+V² log V) | No negative cycles |
| Kruskal | MST | O(E log V) | — |
| Prim (heap) | MST | O(E log V) | — |
| Kosaraju/Tarjan | SCC | O(V+E) | Directed graph |
| Kahn’s / DFS | Topological sort | O(V+E) | DAG |
| Edmonds-Karp | Max flow | O(VE²) | — |
9. GATE Examples
BFS discovers level by level. Count vertices reached in exactly 2 BFS steps = depends on graph structure. Key: BFS gives exact levels.
Bellman-Ford needs V−1 = 3 passes to guarantee correctness. Answer: 3 passes.
Sort edges by weight. Add greedy: edge (u,v) added if u and v in different components. Skip if same component (would create cycle). MST = V−1 edges.
10. Common Mistakes
- Using Dijkstra with negative edges: Gives incorrect results. Use Bellman-Ford (O(VE)) for negative edges.
- Topological sort on cyclic graphs: Topological sort is undefined for graphs with cycles. Kahn’s algorithm detects this: if processed < V vertices, a cycle exists.
- SCC defined for undirected graphs: For undirected, use connected components (BFS/DFS). SCC applies to directed graphs only.
- MST is unique only if all edge weights are distinct: Equal weight edges may produce multiple valid MSTs with the same total weight.
- Floyd-Warshall initialisation: dist[i][i]=0 (not ∞), and missing edges get ∞. Forgetting this causes incorrect results.
11. FAQ
- What is the difference between BFS and DFS?
- BFS explores by levels using a queue, guaranteeing shortest path in unweighted graphs. DFS explores as deep as possible using a stack or recursion, useful for cycle detection, topological sort, and SCC. Both have O(V+E) time on adjacency lists.
- When to use Dijkstra vs Bellman-Ford vs Floyd-Warshall?
- Dijkstra: single source, non-negative edges, O((V+E)log V). Bellman-Ford: single source with possible negative edges, O(VE), detects negative cycles. Floyd-Warshall: all-pairs shortest paths, O(V³), handles negative edges, detects negative cycles.
- How does Kosaraju’s algorithm find SCCs?
- Pass 1: DFS on original graph, record finish times (push to stack). Pass 2: transpose the graph. Pop vertices from stack and run DFS on transposed graph; each DFS tree is exactly one SCC. Correctness relies on the fact that in the transposed graph, SCCs are the same but edges between them are reversed.
- What is the maximum flow minimum cut theorem?
- In any flow network, the maximum value of an s-t flow equals the minimum capacity of any s-t cut (partition of vertices into S containing s and T containing t). This duality enables computing max flow and min cut simultaneously via Ford-Fulkerson.