Applications: Shortest Paths, Components, Topological Sort

Three classic problems solved by BFS or DFS in linear time: shortest paths in an unweighted graph (BFS), counting connected components (BFS or DFS), and topological sort of a DAG (DFS finish-time order or Kahn's BFS-style algorithm).

Three problems, two algorithms

Each of these three classic problems reduces to a single BFS or DFS pass. None requires more than the linear-time traversals you have already seen — but the trick is in how you read off the answer from the traversal.

Shortest path (unweighted graph) — BFS, since each layer = one extra edge.
Connected components — BFS or DFS, run from every unvisited vertex; the number of restarts is the component count.
Topological sort (on a DAG) — DFS, ordered by decreasing finish time; equivalent to Kahn's algorithm, a BFS over vertices with zero in-degree.

1. Shortest paths in an unweighted graph

On an unweighted graph, every edge counts as one step. BFS explores in layers — layer k = all vertices at distance exactly k — so the first time it reaches a vertex is via a shortest path.

Algorithm: run BFS from the source s, recording dist[v] = dist[parent] + 1. To recover the path itself, also store parent[v] and walk it backward from the destination.

Step-by-step trace on the same graph as the BFS chapter, BFS from 1:

Example

(1)───(2)───(5)

│ │

(3)───(4)───(6)

Step Q (front..back) dist (positions 1..6) newly discovered

start [1] 0 ∞ ∞ ∞ ∞ ∞ (1)

pop 1 [2,3] 0 1 1 ∞ ∞ ∞ (2,3)

pop 2 [3,4,5] 0 1 1 2 2 ∞ (4,5)

pop 3 [4,5] 0 1 1 2 2 ∞ —

pop 4 [5,6] 0 1 1 2 2 3 (6)

pop 5 [6] 0 1 1 2 2 3 —

pop 6 [] 0 1 1 2 2 3 —

dist[6] = 3, and parent gives the shortest path 1 → 2 → 4 → 6.

For weighted graphs: BFS no longer works because layer order no longer corresponds to total weight. Use Dijkstra (non-negative weights) or Bellman–Ford (general weights).

2. Counting connected components

A connected component of an undirected graph is a maximal set of vertices reachable from each other. The algorithm is the simplest application of BFS/DFS:

Example

components = 0

for each vertex v:

if v is unvisited:

components += 1

BFS (or DFS) from v — this marks the whole component

Each restart kicks off exploration of a brand-new component, so the number of restarts is the number of components. Often we also record comp[v] — the component ID — so we can answer 'are u and v connected?' in O(1) afterwards.

Step-by-step on a disconnected graph:

Example

Graph: (1)──(2) (3)──(4)──(5) (6)

v=1 unvisited → components=1, DFS marks {1, 2} comp = [_, 1, 1, _, _, _, _]

v=2 visited → skip

v=3 unvisited → components=2, DFS marks {3, 4, 5} comp = [_, 1, 1, 2, 2, 2, _]

v=4, 5 visited → skip

v=6 unvisited → components=3, DFS marks {6} comp = [_, 1, 1, 2, 2, 2, 3]

Result: 3 components.

For directed graphs the analogous concept is strongly connected components (SCC), which requires Tarjan's or Kosaraju's algorithm — beyond this section, but built on the same DFS skeleton.

3. Topological sort of a DAG

A topological sort of a directed acyclic graph (DAG) is a linear ordering of its vertices such that for every edge u → v, vertex u appears before v in the ordering. Useful any time something must be done in dependency order — course prerequisites, build systems, task scheduling.

There are two standard approaches, both linear time:

(a) DFS-based. Run DFS. When a vertex finishes (its recursive call returns), push it onto a stack. After DFS is done, popping the stack gives a valid topological order.

Why it works: if u → v exists, the recursion at u recurses into v (or v was finished earlier), so fin[v] < fin[u] — u finishes after v. Sorting by decreasing finish time puts u before v.

(b) Kahn's algorithm (BFS-based). Maintain inDeg[v]. Initialize a queue with every vertex of in-degree 0. Repeatedly pop a vertex u, append it to the output, and decrement inDeg[v] for each neighbor v; whenever inDeg[v] hits 0, enqueue v. If you eventually output fewer than V vertices, the graph has a cycle.

Step-by-step with Kahn's algorithm on a course-dependency DAG:

Example

Graph (edges: u → v means u must come before v):

(1) → (2) → (4)

│ │

▼ ▼

(3) → (5) → (6)

In-degrees: in[1]=0, in[2]=1, in[3]=1, in[4]=1, in[5]=1, in[6]=2

Start: queue = [1] output = []

Pop 1: output = [1] in[2]→0, in[3]→0 queue = [2, 3]

Pop 2: output = [1,2] in[4]→0 queue = [3, 4]

Pop 3: output = [1,2,3] in[5]→0 queue = [4, 5]

Pop 4: output = [1,2,3,4] in[6]→1 queue = [5]

Pop 5: output = [1,2,3,4,5] in[6]→0 queue = [6]

Pop 6: output = [1,2,3,4,5,6] queue = []

All 6 vertices were emitted, so the graph is a DAG and the output is a valid topological order:

Example

This run: 1, 2, 3, 4, 5, 6

Another: 1, 3, 2, 5, 4, 6 (also valid — topological orders aren't unique)

Kahn's algorithm doubles as a cycle detector: if |output| < V at the end, some vertices never reached in-degree 0, which means they sit on a cycle.

Pseudocode

All three solutions side by side: BFS shortest paths with parent tracking, component counting by restarting the traversal, and both topological-sort variants — DFS finish times and Kahn's in-degree queue. Each is a self-contained function in the C++ tab; pick whichever fits the problem you're solving.

1// 1. Unweighted shortest paths from s
2BFS-SHORTEST-PATHS(G, s):
3    for each v in G: dist[v] = ∞, parent[v] = NIL
4    dist[s] = 0; enqueue(Q, s)
5    while Q not empty:
6        u = dequeue(Q)
7        for each neighbor v of u:
8            if dist[v] == ∞:
9                dist[v] = dist[u] + 1
10                parent[v] = u
11                enqueue(Q, v)
12    return dist, parent
13
14// 2. Count connected components (undirected graph)
15COUNT-COMPONENTS(G):
16    visited[v] = false for all v
17    count = 0
18    for each v in G:
19        if not visited[v]:
20            count = count + 1
21            BFS or DFS from v — mark every reached vertex visited
22    return count
23
24// 3a. Topological sort via DFS finish times
25TOPO-SORT-DFS(G):
26    order = empty stack
27    visited[v] = false for all v
28    for each v in G:
29        if not visited[v]: DFS-VISIT(v, order)
30    return order popped one at a time (top first)
31
32DFS-VISIT(u, order):
33    visited[u] = true
34    for each neighbor v of u:
35        if not visited[v]: DFS-VISIT(v, order)
36    push u onto order        // u finishes — append to stack
37
38// 3b. Topological sort via Kahn (BFS on in-degrees)
39TOPO-SORT-KAHN(G):
40    compute inDeg[v] for all v
41    Q = queue of all v with inDeg[v] = 0
42    order = []
43    while Q not empty:
44        u = dequeue(Q)
45        append u to order
46        for each neighbor v of u:
47            inDeg[v] -= 1
48            if inDeg[v] == 0: enqueue(Q, v)
49    if |order| < V: report "cycle"
50    return order

Complexity summary

All three applications inherit the cost of one BFS or DFS pass plus O(V) bookkeeping.

Problem	Algorithm	Time	Space
Unweighted shortest paths from `s`	BFS	O(V + E)	O(V)
Connected components	BFS or DFS, restarted on each unvisited vertex	O(V + E)	O(V)
Topological sort	DFS (finish times) or Kahn (BFS on in-degrees)	O(V + E)	O(V)

No trick — every vertex is processed once and every edge inspected a constant number of times.

Complexity Analysis

Time Complexity

All three applications run in O(V + E) on a graph stored as an adjacency list.

Space Complexity

O(V) extra for the queue/stack and the dist / visited / inDeg arrays.

BFS-based shortest paths only work in unweighted graphs (or uniform-weight ones). Topological sort exists iff the graph is a DAG — both Kahn's and DFS-based versions naturally detect the presence of a cycle.

Growth Rate Comparison

Three problems, two algorithms

Shortest path (unweighted graph) — BFS, since each layer = one extra edge.
Connected components — BFS or DFS, run from every unvisited vertex; the number of restarts is the component count.
Topological sort (on a DAG) — DFS, ordered by decreasing finish time; equivalent to Kahn's algorithm, a BFS over vertices with zero in-degree.

1. Shortest paths in an unweighted graph

Algorithm: run BFS from the source s, recording dist[v] = dist[parent] + 1. To recover the path itself, also store parent[v] and walk it backward from the destination.

Step-by-step trace on the same graph as the BFS chapter, BFS from 1:

Example

(1)───(2)───(5)

│ │

(3)───(4)───(6)

Step Q (front..back) dist (positions 1..6) newly discovered

start [1] 0 ∞ ∞ ∞ ∞ ∞ (1)

pop 1 [2,3] 0 1 1 ∞ ∞ ∞ (2,3)

pop 2 [3,4,5] 0 1 1 2 2 ∞ (4,5)

pop 3 [4,5] 0 1 1 2 2 ∞ —

pop 4 [5,6] 0 1 1 2 2 3 (6)

pop 5 [6] 0 1 1 2 2 3 —

pop 6 [] 0 1 1 2 2 3 —

dist[6] = 3, and parent gives the shortest path 1 → 2 → 4 → 6.

For weighted graphs: BFS no longer works because layer order no longer corresponds to total weight. Use Dijkstra (non-negative weights) or Bellman–Ford (general weights).

2. Counting connected components

A connected component of an undirected graph is a maximal set of vertices reachable from each other. The algorithm is the simplest application of BFS/DFS:

Example

components = 0

for each vertex v:

if v is unvisited:

components += 1

BFS (or DFS) from v — this marks the whole component

Step-by-step on a disconnected graph:

Example

Graph: (1)──(2) (3)──(4)──(5) (6)

v=1 unvisited → components=1, DFS marks {1, 2} comp = [_, 1, 1, _, _, _, _]

v=2 visited → skip

v=3 unvisited → components=2, DFS marks {3, 4, 5} comp = [_, 1, 1, 2, 2, 2, _]

v=4, 5 visited → skip

v=6 unvisited → components=3, DFS marks {6} comp = [_, 1, 1, 2, 2, 2, 3]

Result: 3 components.

For directed graphs the analogous concept is strongly connected components (SCC), which requires Tarjan's or Kosaraju's algorithm — beyond this section, but built on the same DFS skeleton.

3. Topological sort of a DAG

There are two standard approaches, both linear time:

(a) DFS-based. Run DFS. When a vertex finishes (its recursive call returns), push it onto a stack. After DFS is done, popping the stack gives a valid topological order.

Why it works: if u → v exists, the recursion at u recurses into v (or v was finished earlier), so fin[v] < fin[u] — u finishes after v. Sorting by decreasing finish time puts u before v.

Step-by-step with Kahn's algorithm on a course-dependency DAG:

Example

Graph (edges: u → v means u must come before v):

(1) → (2) → (4)

│ │

▼ ▼

(3) → (5) → (6)

In-degrees: in[1]=0, in[2]=1, in[3]=1, in[4]=1, in[5]=1, in[6]=2

Start: queue = [1] output = []

Pop 1: output = [1] in[2]→0, in[3]→0 queue = [2, 3]

Pop 2: output = [1,2] in[4]→0 queue = [3, 4]

Pop 3: output = [1,2,3] in[5]→0 queue = [4, 5]

Pop 4: output = [1,2,3,4] in[6]→1 queue = [5]

Pop 5: output = [1,2,3,4,5] in[6]→0 queue = [6]

Pop 6: output = [1,2,3,4,5,6] queue = []

All 6 vertices were emitted, so the graph is a DAG and the output is a valid topological order:

Example

This run: 1, 2, 3, 4, 5, 6

Another: 1, 3, 2, 5, 4, 6 (also valid — topological orders aren't unique)

Kahn's algorithm doubles as a cycle detector: if |output| < V at the end, some vertices never reached in-degree 0, which means they sit on a cycle.

Pseudocode

1// 1. Unweighted shortest paths from s
2BFS-SHORTEST-PATHS(G, s):
3    for each v in G: dist[v] = ∞, parent[v] = NIL
4    dist[s] = 0; enqueue(Q, s)
5    while Q not empty:
6        u = dequeue(Q)
7        for each neighbor v of u:
8            if dist[v] == ∞:
9                dist[v] = dist[u] + 1
10                parent[v] = u
11                enqueue(Q, v)
12    return dist, parent
13
14// 2. Count connected components (undirected graph)
15COUNT-COMPONENTS(G):
16    visited[v] = false for all v
17    count = 0
18    for each v in G:
19        if not visited[v]:
20            count = count + 1
21            BFS or DFS from v — mark every reached vertex visited
22    return count
23
24// 3a. Topological sort via DFS finish times
25TOPO-SORT-DFS(G):
26    order = empty stack
27    visited[v] = false for all v
28    for each v in G:
29        if not visited[v]: DFS-VISIT(v, order)
30    return order popped one at a time (top first)
31
32DFS-VISIT(u, order):
33    visited[u] = true
34    for each neighbor v of u:
35        if not visited[v]: DFS-VISIT(v, order)
36    push u onto order        // u finishes — append to stack
37
38// 3b. Topological sort via Kahn (BFS on in-degrees)
39TOPO-SORT-KAHN(G):
40    compute inDeg[v] for all v
41    Q = queue of all v with inDeg[v] = 0
42    order = []
43    while Q not empty:
44        u = dequeue(Q)
45        append u to order
46        for each neighbor v of u:
47            inDeg[v] -= 1
48            if inDeg[v] == 0: enqueue(Q, v)
49    if |order| < V: report "cycle"
50    return order

Complexity summary

All three applications inherit the cost of one BFS or DFS pass plus O(V) bookkeeping.

Problem	Algorithm	Time	Space
Unweighted shortest paths from `s`	BFS	O(V + E)	O(V)
Connected components	BFS or DFS, restarted on each unvisited vertex	O(V + E)	O(V)
Topological sort	DFS (finish times) or Kahn (BFS on in-degrees)	O(V + E)	O(V)

No trick — every vertex is processed once and every edge inspected a constant number of times.

Complexity Analysis

Time Complexity

All three applications run in O(V + E) on a graph stored as an adjacency list.

Space Complexity

O(V) extra for the queue/stack and the dist / visited / inDeg arrays.