Graph Algorithms: Dijkstra, Topological Sort, Cycles, Components
Weighted shortest paths with Dijkstra, ordering tasks with topological sort, detecting cycles, and counting connected components.
advanced60 min#dijkstra#topological-sort#cycle-detection#connected-components#shortest-path
Prerequisites: Graphs: Representations, BFS and DFS, Heaps and Priority Queues
Why it matters
BFS and DFS tell you what is reachable. Real systems ask sharper questions. What is the cheapest route when roads have different lengths? In what order should a build system compile packages so that every dependency comes first? Can this set of course prerequisites ever be satisfied? How many separate clusters does this network contain? Four algorithms cover these cases, and each is a small twist on the traversals you already know.
Intuition
- Dijkstra is BFS for weighted graphs. Instead of a plain queue, a priority queue always expands the closest unexplored vertex next. Once a vertex is the closest one left, nothing cheaper can reach it later, because all weights are non-negative.
- Topological sort lines up the tasks of a directed acyclic graph (DAG) so every arrow points forward. Picture getting dressed: socks before shoes. Repeatedly do whatever has no unmet prerequisites.
- Cycle detection asks whether following arrows can bring you back to where you started. If so, no valid order exists (shoes need socks, socks need shoes).
- Connected components groups vertices into islands: start a traversal at any unvisited vertex, and everything it touches is one island.
How it works
Dijkstra. Keep dist[v], the best known distance from the source, initially infinity except the source at 0. Push (0, source) into a min-heap. Repeatedly pop the smallest (d, u). If d is larger than the recorded dist[u], it is a stale duplicate: skip it. Otherwise relax each edge (u, v, w): if d + w beats dist[v], update it and push the new pair. With a binary heap the cost is O((V + E) log V). It requires non-negative weights; with negative edges use Bellman-Ford. Dijkstra computes distances, and to recover the route you also store each vertex's predecessor when you relax.
Dijkstra on the same roads as the code. Labels are the best known distance so far, green is the vertex being expanded, amber vertices just received a new distance, and highlighted edges form the best route found so far. Notice B improves from 4 to 3 once the cheaper detour through C is discovered.
Topological sort (Kahn's algorithm). Compute each vertex's in-degree (number of incoming edges). Put all vertices with in-degree 0 in a queue. Pop one, append it to the output, and decrement the in-degree of each neighbor, queueing any that reach 0. If the output contains fewer than V vertices, the leftover vertices sit on a cycle. The DFS alternative records vertices in reverse finishing order. Both take O(V + E). The order is usually not unique.
Kahn's algorithm. Green is the vertex just popped, amber vertices are waiting in the queue, faded vertices are already in the output, and highlighted edges are the ones just removed. The vertices come out in an order where every arrow points to the right.
Cycle detection.
-
Directed graphs: DFS with three colors. White is unvisited, gray is on the current recursion path, black is finished. Meeting a gray vertex means you found a back edge, a cycle. Meeting a black one is harmless (a different branch already finished). Kahn's algorithm doubles as a detector: fewer than V outputs means a cycle.
-
Undirected graphs: DFS or BFS, and a cycle exists if you reach a visited vertex that is not the one you just came from. Union-find (a later lesson) is another standard tool.
Three-color cycle detection on a directed triangle. Amber vertices are gray (on the DFS path), and the final highlighted edge is the back edge that reveals the cycle.
Connected components. For each vertex not yet seen, run a traversal and collect everything it reaches. The number of traversals started equals the number of components. O(V + E). For directed graphs, the analogous notion is strongly connected components, a more advanced topic.
Counting connected components. Green is the component the current traversal discovers, amber vertices belong to components found earlier. Each new traversal starts only at a vertex that is still unseen.
| Operation | Time | Notes |
|---|---|---|
| Dijkstra (binary heap) | O((V + E) log V) | Non-negative weights only |
| Topological sort (Kahn or DFS) | O(V + E) | DAG only |
| Cycle detection (DFS) | O(V + E) | Colors for directed graphs |
| Connected components | O(V + E) | One traversal per component |
| Extra space | O(V) | Distances, in-degrees, seen set |
Code: all four
import heapq
import json
from collections import deque
def show(*xs):
print(*(json.dumps(x, separators=(',', ':')) for x in xs))
def dijkstra(graph, src):
dist = {src: 0}
pq = [(0, src)]
while pq:
d, u = heapq.heappop(pq)
if d > dist.get(u, float("inf")):
continue # stale entry
for v, w in graph.get(u, []):
nd = d + w
if nd < dist.get(v, float("inf")):
dist[v] = nd
heapq.heappush(pq, (nd, v))
return dist
def topo_sort(n, edges):
"""Kahn's algorithm; returns None if the graph has a cycle."""
adj = [[] for _ in range(n)]
indeg = [0] * n
for u, v in edges:
adj[u].append(v)
indeg[v] += 1
q = deque(i for i in range(n) if indeg[i] == 0)
order = []
while q:
u = q.popleft()
order.append(u)
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return order if len(order) == n else None
def has_cycle(n, edges):
"""Directed graph: DFS with colors 0=new, 1=on current path, 2=done."""
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
color = [0] * n
def visit(u):
color[u] = 1
for v in adj[u]:
if color[v] == 1 or (color[v] == 0 and visit(v)):
return True
color[u] = 2
return False
return any(color[i] == 0 and visit(i) for i in range(n))
def components(n, edges):
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
seen, comps = set(), []
for s in range(n):
if s in seen:
continue
seen.add(s)
stack, comp = [s], []
while stack:
u = stack.pop()
comp.append(u)
for v in adj[u]:
if v not in seen:
seen.add(v)
stack.append(v)
comps.append(sorted(comp))
return comps
roads = {
"A": [("B", 4), ("C", 1)],
"C": [("B", 2), ("D", 7)],
"B": [("D", 1)],
}
show(dijkstra(roads, "A"))
deps = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]
show(topo_sort(5, deps))
show(topo_sort(3, [(0, 1), (1, 2), (2, 0)]))
show(has_cycle(5, deps), has_cycle(3, [(0, 1), (1, 2), (2, 0)]))
show(components(7, [(0, 1), (1, 2), (3, 4)]))const show = (...xs) => console.log(xs.map((x) => JSON.stringify(x)).join(" "));
// Minimal binary min-heap of [priority, value] pairs.
class PQ {
constructor() {
this.a = [];
}
get size() {
return this.a.length;
}
push(item) {
const a = this.a;
a.push(item);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (a[p][0] <= a[i][0]) break;
[a[p], a[i]] = [a[i], a[p]];
i = p;
}
}
pop() {
const a = this.a;
const top = a[0];
const last = a.pop();
if (a.length) {
a[0] = last;
let i = 0;
while (true) {
let s = i;
for (const c of [2 * i + 1, 2 * i + 2]) {
if (c < a.length && a[c][0] < a[s][0]) s = c;
}
if (s === i) break;
[a[i], a[s]] = [a[s], a[i]];
i = s;
}
}
return top;
}
}
function dijkstra(graph, src) {
const dist = { [src]: 0 };
const pq = new PQ();
pq.push([0, src]);
while (pq.size) {
const [d, u] = pq.pop();
if (d > (dist[u] ?? Infinity)) continue; // stale entry
for (const [v, w] of graph[u] ?? []) {
const nd = d + w;
if (nd < (dist[v] ?? Infinity)) {
dist[v] = nd;
pq.push([nd, v]);
}
}
}
return dist;
}
// Kahn's algorithm; returns null if the graph has a cycle.
function topoSort(n, edges) {
const adj = Array.from({ length: n }, () => []);
const indeg = new Array(n).fill(0);
for (const [u, v] of edges) {
adj[u].push(v);
indeg[v]++;
}
const queue = [];
for (let i = 0; i < n; i++) if (indeg[i] === 0) queue.push(i);
const order = [];
for (let head = 0; head < queue.length; head++) {
const u = queue[head];
order.push(u);
for (const v of adj[u]) {
if (--indeg[v] === 0) queue.push(v);
}
}
return order.length === n ? order : null;
}
// Directed graph: DFS with colors 0=new, 1=on current path, 2=done.
function hasCycle(n, edges) {
const adj = Array.from({ length: n }, () => []);
for (const [u, v] of edges) adj[u].push(v);
const color = new Array(n).fill(0);
const visit = (u) => {
color[u] = 1;
for (const v of adj[u]) {
if (color[v] === 1 || (color[v] === 0 && visit(v))) return true;
}
color[u] = 2;
return false;
};
for (let i = 0; i < n; i++) if (color[i] === 0 && visit(i)) return true;
return false;
}
function components(n, edges) {
const adj = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
}
const seen = new Set();
const comps = [];
for (let s = 0; s < n; s++) {
if (seen.has(s)) continue;
seen.add(s);
const stack = [s];
const comp = [];
while (stack.length) {
const u = stack.pop();
comp.push(u);
for (const v of adj[u]) {
if (!seen.has(v)) {
seen.add(v);
stack.push(v);
}
}
}
comps.push(comp.sort((a, b) => a - b));
}
return comps;
}
const roads = {
A: [["B", 4], ["C", 1]],
C: [["B", 2], ["D", 7]],
B: [["D", 1]],
};
show(dijkstra(roads, "A"));
const deps = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]];
show(topoSort(5, deps));
show(topoSort(3, [[0, 1], [1, 2], [2, 0]]));
show(hasCycle(5, deps), hasCycle(3, [[0, 1], [1, 2], [2, 0]]));
show(components(7, [[0, 1], [1, 2], [3, 4]]));Both versions print:
{"A":0,"B":3,"C":1,"D":4}
[0,1,2,3,4]
null
false true
[[0,1,2],[3,4],[5],[6]]
Dijkstra finds that B costs 3 (via C: 1 + 2, beating the direct edge of 4) and D costs 4 (via B). The dependency graph orders as 0, 1, 2, 3, 4. The three-node ring has no topological order, so the result is empty (None or null), and the cycle check agrees: the first graph has none, the second does. The seven vertices split into components 0-1-2, 3-4, and the isolated 5 and 6.
Common pitfalls
- Skipping the stale-entry check: without
if d > dist[u]: continuethe algorithm still gives right answers but can reprocess vertices many times. - Using BFS on weighted edges: BFS counts edges, not cost. A path with fewer edges can be longer.
- Confusing cycle detection rules: in a directed graph, seeing an already-visited vertex is not a cycle by itself; it must be on the current path (gray). In an undirected graph, the edge back to your parent is not a cycle.
- Forgetting disconnected vertices: Kahn's algorithm and the cycle check must start from every vertex, not just one.
- Assuming a unique topological order: tests that compare exact output fail when valid alternatives exist. Check the ordering property instead.
- Unreachable vertices in Dijkstra: they never receive a distance. Decide whether to report infinity or omit them.
Practice
Number of connected components easy
Hint
Count how many fresh traversals you need to start.
Show solution
Build the adjacency list, loop over vertices, and start a DFS or BFS at each unseen one, incrementing a counter. O(V + E). Union-find offers the same answer with a different mechanism.
Course schedule (can all courses be finished?) medium
Hint
Prerequisites form a directed graph. When is a valid order impossible?
Show solution
Build edges from prerequisite to course and run Kahn's algorithm. All courses can be finished exactly when the output contains every course, meaning there is no cycle. For the ordering itself, return the output list. O(V + E).
Network delay time medium
Hint
You want the farthest of the shortest distances from the source.
Show solution
Run Dijkstra from the source. If any vertex is unreachable, return -1; otherwise the answer is the maximum value in the distance map, since a signal reaches everyone only when the slowest path arrives. O((V + E) log V).
Shortest path with the route, not just the cost hard
Hint
Remember who last improved each vertex.
Show solution
Keep a prev map. Whenever relaxing an edge improves dist[v], set prev[v] = u. After the algorithm, walk back from the target through prev until the source, then reverse the list. The extra space is O(V) and the time is unchanged.
Interview questions
- Why does Dijkstra fail with negative edges? It finalizes the closest vertex on the assumption nothing can improve it later, which only holds when weights are non-negative.
- What is the complexity of Dijkstra? O((V + E) log V) with a binary heap.
- How do you detect a cycle in a directed graph? DFS with a gray (on-path) state, or Kahn's algorithm leaving vertices unprocessed.
- What does a topological order exist for? Exactly the directed acyclic graphs. Cyclic graphs have none.
- BFS or Dijkstra? BFS when all edges cost the same, Dijkstra when weights differ and are non-negative.
Interviewers look for: naming the right algorithm from the problem statement (weights? directed? cycles?), stating preconditions like non-negative weights, and discussing the lazy-deletion trick with the priority queue.
Quick check
Every task in a build graph has been processed except tasks C and D, which each wait on the other. What does Kahn's algorithm report?
Finished this lesson?
Further resources
- Dijkstra's algorithm (Wikipedia) (article)
- Topological sorting (Wikipedia) (article)
- Connected component (Wikipedia) (article)