Topological Sorting and DAG Algorithms

Kahn's indegree algorithm and DFS finishing-time algorithm.

Algorithms

Kahn's indegree algorithm and DFS finishing-time algorithm.

Applications

Course scheduling, dependency resolution, build systems, task ordering, DAG shortest/longest paths, and critical-path analysis.

Cycle handling

A topological ordering exists only for a DAG. Detect a cycle when Kahn's algorithm processes fewer than V vertices or when DFS finds a back edge in a directed graph.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

A DAG can have many valid topological orders; Kahn's algorithm with a min-heap returns the lexicographically smallest. Relaxing edges in topological order gives shortest or longest paths in O(V + E) — even with negative weights — because every predecessor is final before its successors are processed. The longest path is the project's critical path: delaying any task on it delays the whole project.

#include <bits/stdc++.h>
using namespace std;

vector<int> kahn(int V, const vector<vector<int>>& adj) {
    vector<int> indeg(V, 0), order;
    for (auto& l : adj) for (int v : l) ++indeg[v];
    priority_queue<int, vector<int>, greater<int>> ready;          // smallest label first: deterministic order
    for (int u = 0; u < V; ++u) if (!indeg[u]) ready.push(u);
    while (!ready.empty()) {
        int u = ready.top(); ready.pop(); order.push_back(u);
        for (int v : adj[u]) if (--indeg[v] == 0) ready.push(v);
    }
    return order;                                                  // size < V means a cycle
}
bool dfsTopo(int V, const vector<vector<int>>& adj, vector<int>& order) {
    vector<int> color(V, 0);                                       // 0 white, 1 on stack (gray), 2 done
    bool cyclic = false;
    function<void(int)> dfs = [&](int u) {
        color[u] = 1;
        for (int v : adj[u]) { if (color[v] == 1) cyclic = true; else if (!color[v]) dfs(v); }
        color[u] = 2; order.push_back(u);                          // finished
    };
    for (int u = 0; u < V; ++u) if (!color[u]) dfs(u);
    reverse(order.begin(), order.end());
    return !cyclic;
}

int mai
…

Kahn order: setup compile docs test package release
DFS finishing order reversed: setup docs compile test package release
project length 11, critical path: setup compile test package release
cycle 0->1->2->0: Kahn processed 0 of 3 vertices; DFS acyclic = false

Quiz

? Kahn's algorithm processed 0 of 3 vertices. What does that mean?
+ The graph has a cycle — no vertex ever reached indegree 0 :: Fewer than V processed means a cycle.
- The graph is empty. :: It had 3 vertices.
- The order is reversed. :: No order exists.
- A bug. :: Expected behaviour.

? In DFS-based topological sort, why is the finishing order reversed?
+ A vertex finishes only after all its descendants, so reversing puts every vertex before them. :: Reverse postorder.
- To sort by label. :: No.
- Because DFS visits sinks first. :: Partly true; the reversal is the point.
- It does not need reversing. :: It does.

? Which problems are solved by relaxing edges in topological order? (select all that apply)
+ Shortest paths in a DAG with negative weights :: Each vertex is final before it is used.
+ Longest path (critical path) in a DAG :: Same relaxation with max.
- Shortest paths in a graph with cycles :: Needs Dijkstra or Bellman–Ford.
+ Counting paths in a DAG :: Sum over predecessors.