Connectivity: Topological Sort, SCC & Bridges — Algorithms Course

What you'll learn

Beyond visiting vertices, traversal reveals a graph's structure: the order to do dependent tasks, the tightly-knit clusters, and the single edges or vertices whose removal splits the graph apart.

By the end you'll be able to:

Produce a topological order of a DAG and detect cycles
Find strongly connected components
Locate bridges and articulation points

Topological sort

A directed acyclic graph (DAG) models dependencies: an edge u → v means "u must come before v." A topological sort is a linear order respecting all edges — the order to compile modules, run build steps, or get dressed:

A dependency DAG and one valid order

Task dependencies (edges point "must come before")

socksshirt

↓

shoestie

↓jacket

A valid order: socks → shirt → shoes → tie → jacket (many orders work).

Kahn's algorithm

Kahn's algorithm repeatedly removes a vertex with no remaining prerequisites (in-degree 0): take it next, delete its outgoing edges, and repeat. If you can't empty the graph, the leftover vertices form a cycle — so this doubles as cycle detection:

Language

topo_sort.py

from collections import deque

def topo_sort(adj, n):
    indeg = [0] * n
    for u in range(n):
        for v in adj[u]:
            indeg[v] += 1
    queue = deque(u for u in range(n) if indeg[u] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1               # remove u's outgoing edges
            if indeg[v] == 0:
                queue.append(v)
    return order if len(order) == n else None   # None => a cycle exists

Note

A DFS-based topological sort also works: push each vertex onto a stack after exploring all its descendants, then reverse the stack. Both are O(V + E).

Strongly connected components

In a directed graph, a strongly connected component (SCC) is a maximal set of vertices where every one can reach every other. Kosaraju's algorithm finds them with two passes: DFS the graph and record finish times, then DFS the transpose (all edges reversed) in decreasing finish order — each tree is one SCC. Tarjan's algorithm does it in a single DFS using low-link numbers. Both are O(V + E).

Key idea

Contracting each SCC to a single node turns any directed graph into a DAG — the "condensation." Many problems on general digraphs reduce to finding SCCs, then working on the resulting DAG.

Bridges & articulation points

In an undirected graph, a bridge is an edge whose removal disconnects the graph, and an articulation point is such a vertex. They mark the weak spots in a network. A single DFS finds them all: track each vertex's discovery time and the earliest-discovered vertex reachable from its subtree (its low-link). An edge is a bridge when a child's subtree can't reach back above the current vertex — all in O(V + E).

Recap & quick check

Key takeaways

A topological sort linearizes a DAG so every edge points forward.
Kahn's algorithm repeatedly removes in-degree-0 vertices; leftovers mean a cycle.
An SCC is a maximal set where every vertex reaches every other (directed graphs).
Kosaraju (two DFS passes) and Tarjan (one pass) find SCCs in O(V + E).
Bridges and articulation points are found with a single low-link DFS.

Quick check

1. What does a topological sort require of the graph?

2. In Kahn's algorithm, which vertex is taken next?

3. How does Kahn's algorithm detect a cycle?

4. A strongly connected component is:

Add weights to the edges and a new question appears: the cheapest route. Next up: Module 26 — Shortest Paths.