GATE/Algorithms/Graph Algorithms (BFS, DFS, Dijkstra, MST)
Sign in to track
Hard22 min readAlgorithms

Graph Algorithms (BFS, DFS, Dijkstra, MST)

Graph algorithms test your understanding of traversal, shortest paths, and spanning trees. GATE frequently asks about time complexities, correctness conditions, and edge cases.

Key Points

  • ·BFS: O(V + E), queue, shortest path in unweighted graphs
  • ·DFS: O(V + E), stack/recursion, cycle detection, topological sort
  • ·Dijkstra: O((V+E) log V) with heap — fails with negative weights
  • ·Bellman-Ford: O(VE), handles negative weights, detects negative cycles
  • ·Prim's MST: O((V+E) log V) — greedy, grows one tree
  • ·Kruskal's MST: O(E log E) — sort edges, union-find

BFS — Exploring Like Ripples in Water

Drop a stone in a pond. The ripples spread outward one ring at a time. BFS explores a graph the same way — all vertices at distance 1 first, then distance 2, then distance 3.

Uses a queue. Mark visited to avoid revisiting.

Graph:
     1
    / \
   2   3
  / \   \
 4   5   6

BFS from 1:
Queue: [1]            Visit 1, add neighbors 2,3
Queue: [2,3]          Visit 2, add neighbors 4,5
Queue: [3,4,5]        Visit 3, add neighbor 6
Queue: [4,5,6]        Visit 4,5,6 — no new neighbors

Order visited: 1, 2, 3, 4, 5, 6
Distances:    0  1  1  2  2  2

Key property: BFS always finds the shortest path (minimum edges) in an unweighted graph.

Time complexity: O(V + E) — each vertex and edge processed once.

DFS — Exploring Like a Maze Runner

Go as deep as possible in one direction before backtracking. Uses a stack (or recursion).

DFS from 1 (same graph, visit left child first):

Visit 1 → go to 2 → go to 4 (dead end)
Backtrack to 2 → go to 5 (dead end)
Backtrack to 1 → go to 3 → go to 6 (dead end)

Order: 1, 2, 4, 5, 3, 6

Discovery time d[v] = when we first visit v Finish time f[v] = when we finish exploring all of v's descendants

d: 1→1, 2→2, 4→3, 5→5, 3→7, 6→8
f: 4→4, 5→6, 2→7... (fill in as you backtrack)

Edge Classification in Directed Graphs

Edge (u,v) Type What it means
v not yet visited Tree edge New discovery
v is ancestor of u Back edge Cycle exists!
v is descendant (already finished) Forward edge Shortcut down
Neither Cross edge Between branches

In undirected graphs, DFS produces only tree edges and back edges.

Dijkstra's Algorithm — Shortest Path with Weights

Like BFS, but uses a priority queue (min-heap) instead of a regular queue — always process the vertex with the current smallest distance next.

Graph with weighted edges:
1--4-->2--1-->4
|          ^
2          |
|          1
v          |
3----3---->

Find shortest path from 1 to all vertices:

dist = [0, ∞, ∞, ∞]
Priority queue: [(0,1)]

Extract (0,1): process neighbors 2 (dist=4), 3 (dist=2)
dist = [0, 4, 2, ∞], PQ: [(2,3),(4,2)]

Extract (2,3): process neighbors 4 (dist=2+3=5, but via 2: 4+1=5 — same)
PQ: [(4,2),(5,4)]

Extract (4,2): process neighbor 4 (dist=4+1=5 — no improvement)
...

Final: dist = [0, 4, 2, 5]

Why fails with negative edges: Once a vertex is extracted from the priority queue, its distance is considered final. A negative edge could offer a shorter path later — but Dijkstra never looks back.

Time with binary heap: O((V + E) log V)

Bellman-Ford — Handling Negative Weights

Relax every edge, V−1 times. After V−1 rounds, shortest paths are correct (assuming no negative cycle).

Why V−1 rounds? A shortest path with no cycles has at most V−1 edges.

For each of V−1 iterations:
    For each edge (u,v,w):
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w

Detecting negative cycles: Run one more (V-th) iteration. If any distance still decreases, a negative cycle exists.

Time: O(VE) — much slower than Dijkstra, but handles negative weights correctly.

Minimum Spanning Tree (MST)

An MST connects all V vertices with V−1 edges and minimum total weight. No cycles.

Prim's Algorithm — Grow One Tree

Start from any vertex. At each step, add the cheapest edge connecting the current tree to a new vertex.

Graph: 1--4--2, 1--2--3, 2--3--3, 2--5--4, 3--1--4

Start at 1. Tree = {1}.
Cheapest edge out: 1-3 (weight 2). Add 3. Tree = {1,3}.
Cheapest edge out: 3-4 (weight 1). Add 4. Tree = {1,3,4}.
Cheapest edge out: 1-2 (weight 4). But 2-3 (weight 3) is cheaper. Add 2. Tree = {1,2,3,4}.
MST edges: {1-3, 3-4, 3-2} with total weight 2+1+3 = 6.

Time with min-heap: O((V + E) log V)

Kruskal's Algorithm — Sort and Union

Sort all edges by weight. Add an edge if it doesn't create a cycle (use Union-Find to check).

Edges sorted: (3,4,w=1), (1,3,w=2), (2,3,w=3), (1,2,w=4), (2,4,w=5)

Add (3,4,1): no cycle. MST edges: {(3,4)}
Add (1,3,2): no cycle. MST edges: {(3,4),(1,3)}
Add (2,3,3): no cycle. MST edges: {(3,4),(1,3),(2,3)}
Add (1,2,4): 1 and 2 already connected! SKIP.
Done: V-1=3 edges. ✓

Time: O(E log E) — dominated by sorting edges.

Both Prim and Kruskal produce the same MST (it's unique when all weights are distinct).

Quick Check

Q1. Why can't Dijkstra handle negative edge weights?

Answer: Dijkstra assumes that once a vertex is extracted (minimum distance found), no shorter path exists. A negative edge could create a shorter path via a vertex processed later.

Q2. Graph has 5 vertices and MST is found. How many edges does MST have?

Answer: V − 1 = 4 edges. An MST on V vertices always has exactly V−1 edges.

Q3. Bellman-Ford runs on a graph with V=5 vertices. How many edge relaxation rounds are needed?

Answer: V − 1 = 4 rounds. The V-th round checks for negative cycles.

Key Formulas

  • Dijkstra (binary heap): O((V + E) log V)
  • Bellman-Ford: O(VE)
  • Floyd-Warshall: O(V³)
  • Prim's / Kruskal's: O((V+E) log V) / O(E log E)

GATE Exam Tips

  • ★Dijkstra fails on negative edges — if the graph has negative weights, use Bellman-Ford
  • ★MST has exactly V-1 edges and is unique when all weights are distinct
  • ★Kahn's topological sort output size < V means cycle — use this to detect DAG
  • ★GATE often asks: is Prim's or Kruskal's better for dense graphs? Prim's (O(V²) with array) for dense

Finished reading this topic?

Mark it complete to track your study progress.

Sign in to track