Topological Sort & Connectivity · Algorithms (DAA)

Topological sort

A topological order of a directed acyclic graph (DAG) lists the vertices so that every edge u → v has u before v. It answers "in what order can I do these tasks?" — course prerequisites, build systems, spreadsheet recalculation, package installation.

Course prerequisites as a DAG. Any topological order is a valid study plan.

Kahn's algorithm (BFS)

Repeatedly output a vertex with in-degree 0 (no remaining prerequisites) and remove its outgoing edges.

C++

#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;

int main() {
    vector<string> name = {"C1", "C2", "DS", "DM", "OOP", "DAA"};
    vector<vector<int>> adj(6);
    int edges[][2] = {{0, 2}, {1, 2}, {2, 5}, {3, 5}, {0, 4}, {2, 4}};
    vector<int> indeg(6, 0);
    for (auto &e : edges) { adj[e[0]].push_back(e[1]); indeg[e[1]]++; }

    queue<int> q;
    for (int v = 0; v < 6; v++) if (indeg[v] == 0) q.push(v);
    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
    }
    if (order.size() < 6) cout << "cycle detected: no topological order" << endl;
    else { cout << "study order:"; for (int v : order) cout << " " << name[v]; cout << endl; }
    return 0;
}

Output

study order: C1 C2 DM DS DAA OOP

Try it Yourself

If some vertices never reach in-degree 0, the graph has a cycle and no topological order exists. Time O(V + E).

DFS-based topological sort

Run DFS; when a vertex finishes (all its descendants are done), push it onto a stack. Reading the stack top-down gives a topological order.

C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<vector<int>> adj(6);
vector<int> state(6, 0);                 // 0 = new, 1 = on the current path, 2 = finished
vector<int> finishOrder;
bool cycle = false;

void dfs(int u) {
    state[u] = 1;
    for (int v : adj[u]) {
        if (state[v] == 1) cycle = true;            // back edge: a directed cycle
        else if (state[v] == 0) dfs(v);
    }
    state[u] = 2;
    finishOrder.push_back(u);
}

int main() {
    vector<string> name = {"C1", "C2", "DS", "DM", "OOP", "DAA"};
    int edges[][2] = {{0, 2}, {1, 2}, {2, 5}, {3, 5}, {0, 4}, {2, 4}};
    for (auto &e : edges) adj[e[0]].push_back(e[1]);
    for (int v = 0; v < 6; v++) if (state[v] == 0) dfs(v);
    cout << "topological order:";
    for (int i = (int)finishOrder.size() - 1; i >= 0; i--) cout << " " << name[finishOrder[i]];
    cout << "\ncycle: " << (cycle ? "yes" : "no") << endl;
    return 0;
}

Output

topological order: DM C2 C1 DS OOP DAA
cycle: no

Try it Yourself

The three DFS states also detect cycles in directed graphs: reaching a vertex that is still on the current path (state 1) means a back edge, hence a cycle.

Connected components

In an undirected graph, run BFS or DFS from each unvisited vertex; each run discovers one connected component. O(V + E).

Strongly connected components

In a directed graph, a strongly connected component (SCC) is a maximal set of vertices where every vertex can reach every other. Kosaraju's algorithm finds all SCCs in O(V + E):

Run DFS on the graph and record vertices by finish time.
Reverse every edge.
Run DFS on the reversed graph in decreasing finish order; each tree found is one SCC.

C++

#include <iostream>
#include <vector>
using namespace std;

int V = 6;
vector<vector<int>> g(V), rg(V);
vector<bool> seen;
vector<int> order, comp;

void dfs1(int u) { seen[u] = true; for (int v : g[u]) if (!seen[v]) dfs1(v); order.push_back(u); }
void dfs2(int u) { seen[u] = true; comp.push_back(u); for (int v : rg[u]) if (!seen[v]) dfs2(v); }

int main() {
    int edges[][2] = {{0, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 4}, {4, 5}, {5, 3}};
    for (auto &e : edges) { g[e[0]].push_back(e[1]); rg[e[1]].push_back(e[0]); }
    seen.assign(V, false);
    for (int v = 0; v < V; v++) if (!seen[v]) dfs1(v);
    seen.assign(V, false);
    for (int i = V - 1; i >= 0; i--)
        if (!seen[order[i]]) {
            comp.clear();
            dfs2(order[i]);
            cout << "SCC:";
            for (int v : comp) cout << " " << v;
            cout << endl;
        }
    return 0;
}

Output

SCC: 0 2 1
SCC: 3 5 4

Try it Yourself

Test yourself

4 questions · pick an answer to check it instantly

1
Which graphs have a topological order?
2
In Kahn's algorithm, which vertices are output first?
3
In DFS on a directed graph, reaching a vertex that is still on the current recursion path means...
4
What is the time complexity of Kosaraju's SCC algorithm?