Graph Algorithms — GATE CS Complete Reference

BFS and DFS — Properties and Applications

BFS (Breadth-First Search)

Algorithm: Visit all neighbours at distance 1 before distance 2, etc. Uses a queue.

Time: O(V + E) | Space: O(V) | Data structure: Queue

GATE-important properties:

BFS tree = shortest path tree for unweighted graphs
BFS can detect cycles in O(V + E)
Level order traversal of trees is BFS
BFS gives shortest path in terms of number of edges (not weight)

DFS (Depth-First Search)

Algorithm: Explore as far as possible before backtracking. Uses stack/recursion.

Time: O(V + E) | Space: O(V) | Data structure: Stack (or recursion)

DFS timestamps — key for GATE:

discovery time d[v]: when first visited
finish time f[v]: when fully explored
d[u] < d[v] < f[v] < f[u] → v is a descendant of u in DFS tree

Edge classification (directed graphs):

Tree edge: v not yet visited
Back edge: v is ancestor of u (indicates cycle in directed graph)
Forward edge: v is descendant but not via tree edge
Cross edge: all other edges

GATE fact: An undirected graph has no forward or cross edges in DFS.

Topological Sort

Valid only for DAGs (Directed Acyclic Graphs).

DFS method: Process vertices in reverse finishing time order.

Kahn's BFS method: Repeatedly remove vertices with in-degree 0.

GATE question type: "What is a valid topological order of the given DAG?"

Example:

DAG: 5→2, 5→0, 4→0, 4→1, 2→3, 3→1
DFS finishing times: 1(5), 2(4), 3(2), 4(3), 5(0)
Topological order: 4, 5, 2, 0, 3, 1 (one valid order)

Shortest Path Algorithms

Dijkstra's Algorithm

Conditions: Non-negative edge weights only.

Method: Greedy — always expand the closest unvisited vertex.

Graph: 0→1(4), 0→2(1), 2→1(2), 1→3(1), 2→3(5)

Step by step (source = 0):
dist: [0, ∞, ∞, ∞]
Extract 0: update 1→4, 2→1
Extract 2 (dist=1): update 1→min(4,1+2)=3, 3→min(∞,1+5)=6
Extract 1 (dist=3): update 3→min(6,3+1)=4
Extract 3 (dist=4): done

Final distances: [0, 3, 1, 4]

GATE trap: Dijkstra fails with negative weights. Use Bellman-Ford instead.

Bellman-Ford Algorithm

Handles: Negative weights; detects negative cycles.

Method: Relax all edges V−1 times. If any edge still relaxes on iteration V, negative cycle exists.

Complexity: O(V × E)

Floyd-Warshall Algorithm

Computes: All-pairs shortest paths.

Method: For each intermediate vertex k, update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).

Complexity: O(V³) | Space: O(V²)

Negative cycle detection: dist[i][i] < 0 after running F-W.

Minimum Spanning Tree (MST)

Definition: A spanning tree with minimum total edge weight.

Kruskal's Algorithm

Sort all edges by weight (O(E log E))
Add edge if it doesn't form a cycle (use Union-Find: O(α(V)) per operation)
Stop when V−1 edges added

Total: O(E log E) = O(E log V)

Prim's Algorithm

Start with any vertex
Greedily add the minimum weight edge connecting tree to non-tree vertex
Use min-heap: O(E log V)

GATE fact: Both algorithms produce the same MST weight, but possibly different trees if tie-breaking differs.

Unique MST: If all edge weights are distinct, MST is unique.

Strongly Connected Components (SCC)

Kosaraju's Algorithm (two DFS passes):

Run DFS on original graph G, record finishing times
Transpose graph Gᵀ
Run DFS on Gᵀ in reverse finishing time order — each DFS tree is one SCC

Tarjan's Algorithm: Single DFS pass using low-link values.

GATE application: "How many SCCs does this directed graph have?"

GATE Practice Questions

Run Dijkstra on graph: {0-1:10, 0-2:3, 1-3:2, 2-1:4, 2-3:8, 3-4:5, 1-4:7}. Find shortest path from 0 to 4.
Find MST using Kruskal for graph with edges: (A-B:4),(A-C:2),(B-C:5),(B-D:10),(C-E:3),(E-D:4),(D-F:11)
Topologically sort: a→b, a→c, b→d, c→d, d→e, b→e
How many back edges appear in DFS of the following directed graph? (typical GATE question)
T(n) = 9T(n/3) + n² — apply Master Theorem

GATE CS - ALGORITHMS:Graph Algorithms — GATE CS Complete Reference