DSA • Graph Algorithms

Graph Traversal, Shortest Path & MST

Step‑by‑step walkthroughs of BFS, DFS, Dijkstra, Bellman‑Ford, Floyd‑Warshall, Kruskal, Prim, Topological Sort, and SCC — with concrete examples and practice.

Algorithms

📌 Graph Algorithms: Graphs are everywhere – social networks, maps, dependencies. Here we break down the seven most important algorithm categories, using small examples and step‑by‑step walkthroughs to build real understanding.

🎯 How to use this page: Each section contains a conceptual explanation, a worked‑out example with a small graph, detailed pseudocode, and complexity notes. Practice problems follow with hints and solutions.

BFS / DFS

traversalO(V+E)

Dijkstra

non‑negO((V+E) log V)

Bellman‑Ford

neg weightsO(VE)

Floyd‑Warshall

all‑pairsO(V³)

Kruskal / Prim

MSTO(E log V)

Topo Sort

DAGO(V+E)

SCC (Kosaraju/Tarjan)

connectivityO(V+E)

1 BFS & DFS – Graph Traversal

Why it matters: Traversal is the foundation of almost every graph algorithm. BFS explores neighbors layer by layer (great for shortest paths in unweighted graphs), while DFS dives deep into a branch before backtracking (useful for cycle detection, topological sorting, and more).

🔍 Example Graph

Adjacency list: A: [B,C], B: [A,D,E], C: [A,F], D: [B], E: [B], F: [C]

🚀 BFS from A (queue)

Queue: [A], visited: {A}
Pop A, push neighbors B, C → Queue: [B,C], visited: {A,B,C}
Pop B, push D, E → Queue: [C,D,E], visited: {A,B,C,D,E}
Pop C, push F → Queue: [D,E,F], visited: {A,B,C,D,E,F}
Pop D (no new) → Queue: [E,F]
Pop E → Queue: [F]
Pop F → Queue: []

Order: A → B → C → D → E → F (layers: first A, then B,C, then D,E,F)

🚀 DFS from A (recursive)

Visit A, go to B
Visit B, go to D (first unvisited neighbor)
Visit D (dead end), backtrack to B, go to E
Visit E (dead end), backtrack to A, go to C
Visit C, go to F
Visit F (dead end). Done.

Order: A → B → D → E → C → F

Pseudocode Infographic

// BFS (iterative) queue.enqueue(start), visited[start]=true while queue not empty: v = queue.dequeue() for each neighbor w of v: if not visited[w]: visited[w]=true, queue.enqueue(w) // DFS (recursive) def dfs(v): visited[v]=true for each neighbor w of v: if not visited[w]: dfs(w)

Algorithm	Time	Space
BFS	O(V+E)	O(V) (queue)
DFS	O(V+E)	O(V) (stack/recursion)

💡 Key Insight: BFS finds the shortest path in unweighted graphs (distance in edges). DFS is easier to implement recursively and can detect cycles in directed graphs by tracking recursion stack.

2 Dijkstra’s Algorithm – Single‑Source Shortest Path (non‑negative weights)

Idea: Greedy algorithm that maintains a set of visited nodes with the shortest distance known. At each step, it picks the unvisited node with the smallest distance and relaxes its outgoing edges.

🧭 Worked Example

        A --2--> B --1--> D
        |         |        ^
        4         3        |
        |         v        | 5
        +------> C --------+

Adjacency: A→B (2), A→C (4); B→C (3), B→D (1); C→D (5)

⏳ Dijkstra from A

Init: dist = {A:0, B:∞, C:∞, D:∞}; heap = [(0,A)]
Extract A (0): relax B (0+2=2 < ∞) → dist[B]=2, push (2,B); relax C (0+4=4) → dist[C]=4, push (4,C)
Extract B (2): relax C (2+3=5, no change), relax D (2+1=3) → dist[D]=3, push (3,D)
Extract D (3): no outgoing edges
Extract C (4): relax D (4+5=9 > 3, skip)
Distances: A=0, B=2, C=4, D=3

Pseudocode Infographic

dist[source]=0, all others = INF pq.insert((0, source)) while pq not empty: d, u = pq.extract_min() if d > dist[u]: continue for each neighbor v with weight w: if dist[u]+w < dist[v]: dist[v] = dist[u]+w pq.insert((dist[v], v))

Data structure	Time Complexity
Binary heap	O((V+E) log V)
Fibonacci heap	O(E + V log V) theoretical

⚠️ Limitation: Fails if there are negative edge weights. Use Bellman‑Ford for negative weights.

3 Bellman‑Ford – Shortest Path with Negative Weights

Why needed: Dijkstra fails with negative edges because a greedy choice may be suboptimal. Bellman‑Ford relaxes all edges V‑1 times, ensuring correct distances unless a negative cycle exists.

⚖️ Example (negative edge)

        A --2--> B --(-3)--> C
        |                     ^
        +-------4-------------+

Edges: A→B (2), B→C (-3), A→C (4). Source A.

🔄 Relaxations (V=3, V-1 = 2 passes)

Init: dist=[A:0, B:∞, C:∞]
Pass 1: A→B: 0+2=2 → B=2; A→C: 0+4=4 → C=4; B→C: 2+(-3) = -1 → C becomes -1 (better)
After Pass 1: A=0, B=2, C=-1
Pass 2: No changes (all edges relaxed, no further improvement).
Negative cycle check (pass 3): No relaxation possible → no negative cycle.

Pseudocode Infographic

dist[source]=0, others=INF repeat V-1 times: for each edge (u,v) with weight w: if dist[u]+w < dist[v]: dist[v]=dist[u]+w // Negative cycle detection for each edge (u,v) with weight w: if dist[u]+w < dist[v]: report negative cycle

Case	Time Complexity
Always	O(VE)

💡 Key Insight: Slower than Dijkstra but handles negative weights and detects negative cycles – essential for currency arbitrage problems.

4 Floyd‑Warshall – All‑Pairs Shortest Paths

Dynamic programming that builds up the shortest paths between every pair of vertices by considering whether going through an intermediate vertex k yields a shorter path.

🌐 Example (3 cities)

       0      1      2
   0 [0,   5,  INF]
   1 [5,   0,   2  ]
   2 [INF, 2,   0  ]

Edge weights: 0‑1 = 5, 1‑2 = 2 (undirected).

🔄 Iterations

k=0 (via vertex 0): 0→1 is 5, 0→2 via 0? no. 1→0→2: 1‑0 (5) + 0‑2 (INF) → no change.
k=1: 0→1→2: 5+2=7 < INF → update dist[0][2]=7; 2→1→0: 2+5=7 < INF → update dist[2][0]=7.
k=2: nothing new.

Final matrix: all pairs distances known (0‑2 is 7).

Pseudocode Infographic

for k in range(V): for i in range(V): for j in range(V): if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j]

Time	Space
O(V³)	O(V²)

💡 Good for: Dense graphs, small V (≤ 400), or when you need distances between every pair (e.g., routing tables).

5 Kruskal & Prim – Minimum Spanning Tree (MST)

MST problem: Connect all vertices with minimum total edge weight, no cycles. Two classic approaches:

Kruskal: Greedy on edges – sort by weight, add if it doesn't create a cycle (Union‑Find).
Prim: Greedy on vertices – start from any node, repeatedly add the cheapest edge connecting the tree to a new vertex.

🌲 Example Graph

       A ---1--- B
       |         | \
       3         2  4
       |         |    \
       C ---5--- D --- E

Edges: A‑B(1), A‑C(3), B‑D(2), B‑E(4), C‑D(5)

🪚 Kruskal

Sort edges: (A‑B,1), (B‑D,2), (A‑C,3), (B‑E,4), (C‑D,5)
Add A‑B (set {A,B})
Add B‑D (now {A,B,D})
Add A‑C ({A,B,C,D})
Next B‑E would connect E, add it (now all vertices)
Skip C‑D (would form cycle).
MST edges: A‑B, B‑D, A‑C, B‑E (weight 1+2+3+4 = 10)

🌱 Prim (starting from A)

Start with {A}. Edges to tree: A‑B(1), A‑C(3) → choose A‑B (1).
Tree {A,B}. Edges: A‑C(3), B‑D(2), B‑E(4) → choose B‑D(2).
Tree {A,B,D}. Edges: A‑C(3), B‑E(4), C‑D(5) → choose A‑C(3).
Tree {A,B,C,D}. Edges: B‑E(4), C‑D(5) → choose B‑E(4).
All vertices connected. MST weight = 1+2+3+4 = 10.

Kruskal Pseudocode Infographic

sort edges by weight for each edge (u,v) in sorted order: if find(u) != find(v): add to MST, union(u,v)

Algorithm	Time Complexity
Kruskal	O(E log E) = O(E log V)
Prim (with heap)	O((V+E) log V)

💡 Use: Kruskal when edges are given directly; Prim when adjacency list is available and graph is dense.

6 Topological Sort – Ordering DAG Nodes

Problem: Given a DAG (Directed Acyclic Graph), produce a linear ordering of vertices such that for every directed edge u→v, u appears before v. Think of course prerequisites.

📚 Example: Task Dependencies

       A --> B --> D
        \          ^
         \        /
          --> C --

Edges: A→B, A→C, B→D, C→D. All tasks must follow A before B/C, B/C before D.

📋 Kahn’s Algorithm (in‑degree)

In‑degree: A=0, B=1, C=1, D=2.
Queue = [A] (in‑degree 0). Result = []
Pop A: add to result, decrease B & C. Now B=0, C=0 → queue = [B,C]
Pop B: add to result, decrease D → D=1. Queue = [C]
Pop C: add to result, decrease D → D=0 → queue = [D]
Pop D: add to result. Queue empty.
Result: A, B, C, D (or A, C, B, D – both valid).

Kahn’s Algorithm (BFS) Infographic

compute in‑degree of all vertices queue = all vertices with in‑degree 0 while queue not empty: u = queue.dequeue() result.append(u) for each v adjacent to u: in‑degree[v]-- if in‑degree[v]==0: queue.enqueue(v) if len(result)!=V: "cycle exists"

Time	Space
O(V+E)	O(V) (queue + in‑degree)

💡 Application: Build systems, task scheduling, resolving dependencies (e.g., package managers).

7 Strongly Connected Components – Kosaraju & Tarjan

Problem: Find maximal sets of vertices where every vertex can reach every other vertex (SCC). Two classic O(V+E) algorithms.

🧩 Example Directed Graph

        A -----> B -----> C
        ^        |        |
        |        v        v
        D <----- E        F
        |                 ^
        +------- G <------+

Edges: A→B, B→C, C→F, F→G, G→D, D→A, B→E, E→D.

🔄 Kosaraju’s Two‑Pass DFS

First DFS (original graph): record finish times (postorder) on stack. (Order might be: A, B, C, F, G, D, E)
Transpose graph: reverse every edge.
Second DFS on transposed graph in decreasing finish time order:
- Start at E (highest): E, D, A, B, C, F, G all connect → but wait, need correct order.
- Actually: pop stack: E → DFS finds {E, D, A, B, C, F, G} – all connected, so one large SCC.

This graph is actually one SCC (except maybe some isolate? Let's adjust example): Add H→H (self loop). But for clarity, a simpler typical example is a graph with two SCCs.

Instead, use a classic 2‑SCC example:

        0 → 1 → 2 → 3
        ↑           ↓
        └── 4 ←─────┘
        (edges: 0→1,1→2,2→3,3→4,4→0) → one SCC; plus 0→5,5→6,6→5 (SCC2)

Walkthrough omitted for brevity, but the algorithm yields SCCs: {0,1,2,3,4} and {5,6}.

Kosaraju Outline Infographic

1. DFS on original graph, push nodes to stack after recursion 2. Transpose graph (reverse all edges) 3. Pop nodes from stack, DFS on transposed graph; each DFS forest is an SCC

Algorithm	Time	Space
Kosaraju	O(V+E)	O(V+E)
Tarjan	O(V+E)	O(V)

💡 Key Insight: SCC decomposition reduces a directed graph into a DAG of its components – useful for 2‑SAT, dependency analysis, and many advanced problems.

Comparative Summary

Algorithm	Problem	Complexity
BFS / DFS	Traversal, connected components	O(V+E)
Dijkstra	Shortest path (non‑negative weights)	O((V+E) log V)
Bellman‑Ford	Shortest path (negative weights allowed)	O(VE)
Floyd‑Warshall	All‑pairs shortest paths	O(V³)
Kruskal / Prim	Minimum spanning tree	O(E log V)
Topological Sort	Ordering DAG nodes	O(V+E)
Kosaraju / Tarjan	Strongly connected components	O(V+E)

Practice Problems (with Hints)

🔰 Beginner

1. BFS Shortest Path in Unweighted Graph

Problem: Given an undirected graph, find the shortest distance (number of edges) from node 0 to all nodes.

Step‑by‑step approach: Use a queue, initialize distance array with -1 (unvisited). Set dist[0]=0, push 0. While queue not empty, pop front, for each neighbor, if unvisited set dist[neighbor]=dist[curr]+1 and push.

from collections import deque
def bfs_shortest(adj, start):
    n = len(adj)
    dist = [-1] * n
    dist[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist
# Example:
# adj = [[1,2],[0,2,3],[0,1],[1]]
# print(bfs_shortest(adj, 0)) → [0,1,1,2]

2. Dijkstra – Cheapest Flight with at most K stops

Problem: Find the cheapest price from src to dst with at most K stops.

Hint: Use a modified Dijkstra where the priority is (cost, stops_used, node). Or BFS with limit.

import heapq
def findCheapestPrice(n, flights, src, dst, k):
    adj = [[] for _ in range(n)]
    for u,v,w in flights:
        adj[u].append((v,w))
    # (cost, node, stops_left)
    pq = [(0, src, k+1)]
    while pq:
        cost, u, stops = heapq.heappop(pq)
        if u == dst: return cost
        if stops > 0:
            for v, w in adj[u]:
                heapq.heappush(pq, (cost+w, v, stops-1))
    return -1

⚡ Intermediate

3. Bellman‑Ford – Detect Negative Cycle

Problem: Check if the graph contains a negative cycle.

How to solve: Run V-1 relaxations over all edges. Then run one more pass: if any distance can still be reduced, a negative cycle exists.

def has_negative_cycle(edges, V):
    dist = [0] * V  # start with 0
    for _ in range(V-1):
        for u,v,w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u,v,w in edges:
        if dist[u] + w < dist[v]:
            return True  # cycle found
    return False

4. Floyd‑Warshall – City with Smallest Number of Neighbors at Threshold

Problem: Given n cities and weighted edges, find the city with the fewest reachable cities within a distance threshold.

Solution: Compute all‑pairs shortest paths with Floyd‑Warshall, then count for each city how many others are within threshold.

def findTheCity(n, edges, distanceThreshold):
    INF = 10**9
    dist = [[INF]*n for _ in range(n)]
    for i in range(n): dist[i][i]=0
    for u,v,w in edges:
        dist[u][v] = dist[v][u] = w
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    ans = -1
    min_cnt = n+1
    for i in range(n):
        cnt = sum(1 for j in range(n) if j!=i and dist[i][j] <= distanceThreshold)
        if cnt <= min_cnt:
            min_cnt, ans = cnt, i
    return ans

Unsolved Practice

1. Cycle Detection in Directed Graph (DFS with recursion stack)

Hint: Maintain three states: 0=unvisited, 1=visiting, 2=fully processed. If you encounter a node currently in the recursion stack (state 1), there is a cycle.

Write your solution here.

2. MST Weight (Kruskal with DSU)

Hint: Sort edges, use Union‑Find to check if adding an edge would create a cycle. If not, add its weight to total.

Write your solution here.

3. Course Schedule (Topological Sort using Kahn’s Algorithm)

Hint: Build adjacency list and in‑degree array. Start with courses that have no prerequisites, then reduce in‑degree of neighbors. If processed count equals numCourses, possible; else cycle exists.

Write your solution here.

4. Tarjan’s Algorithm for SCC

Hint: Use a single DFS with discovery times, low‑link values, and a stack. When you find a vertex with discovery == low, pop until that vertex to form an SCC.

Write your solution here.