SimuVedaAlgorithms Lab Open in the lab

Graphs / Intermediate

Topological Sort (Kahn) Visualizer

Count incoming edges (in-degree). Nodes with in-degree 0 can go first. Removing them frees up more nodes.

Start the Topological Sort (Kahn) simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(V + E)
Average timeO(V + E)
Worst timeO(V + E)
Extra spaceO(V)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Count the incoming edges of every node. The red numbers are these in-degrees.
  2. A has in-degree 0, so nothing must come first. Queue it.
  3. Take A and add it to the order.
  4. Remove A→B. B now has in-degree 0, so queue it.
  5. Remove A→C. C now has in-degree 0, so queue it.
  6. Take B and add it to the order.
  7. Remove B→D. D still waits for 1 more.
  8. Take C and add it to the order.
  9. Remove C→D. D now has in-degree 0, so queue it.
  10. Remove C→F. F now has in-degree 0, so queue it.
  11. Take D and add it to the order.
  12. Remove D→E. E still waits for 1 more.
  13. Take F and add it to the order.
  14. Remove F→E. E now has in-degree 0, so queue it.
  15. Take E and add it to the order.
  16. Done. A valid order: A → B → C → D → F → E.

Try it with your own input →

Topological sort (Kahn) in Java, Python, C++, C and JavaScript

List<Integer> topoSort(int n) {
  int[] indeg = new int[n];
  for (int u = 0; u < n; u++) for (int v : adj[u]) indeg[v]++;
  Queue<Integer> q = new ArrayDeque<>();
  for (int u = 0; u < n; u++) if (indeg[u] == 0) q.add(u);
  List<Integer> order = new ArrayList<>();
  while (!q.isEmpty()) {
    int u = q.poll();
    order.add(u);
    for (int v : adj[u]) {
      if (--indeg[v] == 0) q.add(v);
    }
  }
  return order; // size < n means there is a cycle
}
from collections import deque

def topo_sort(adj):
    n = len(adj)
    indeg = [0] * n
    for u in range(n):
        for v in adj[u]:
            indeg[v] += 1
    q = deque(u for u in range(n) if indeg[u] == 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  # shorter than n means there is a cycle
vector<int> topoSort(const vector<vector<int>>& adj) {
  int n = adj.size();
  vector<int> indeg(n, 0);
  for (int u = 0; u < n; u++) for (int v : adj[u]) indeg[v]++;
  queue<int> q;
  for (int u = 0; u < n; u++) if (indeg[u] == 0) q.push(u);
  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);
    }
  }
  return order; // size < n means there is a cycle
}
#define MAXN 100
int adj[MAXN][MAXN], deg[MAXN];

/* returns how many nodes were ordered; fewer than n means there is a cycle */
int topoSort(int n, int order[]) {
  int indeg[MAXN] = {0};
  for (int u = 0; u < n; u++) for (int k = 0; k < deg[u]; k++) indeg[adj[u][k]]++;
  int q[MAXN], head = 0, tail = 0;
  for (int u = 0; u < n; u++) if (indeg[u] == 0) q[tail++] = u;
  int cnt = 0;
  while (head < tail) {
    int u = q[head++];
    order[cnt++] = u;
    for (int k = 0; k < deg[u]; k++) {
      int v = adj[u][k];
      if (--indeg[v] == 0) q[tail++] = v;
    }
  }
  return cnt;
}
function topoSort(adj) {
  const n = adj.length;
  const indeg = new Array(n).fill(0);
  for (let u = 0; u < n; u++) for (const v of adj[u]) indeg[v]++;
  const q = [];
  for (let u = 0; u < n; u++) if (indeg[u] === 0) q.push(u);
  const order = [];
  while (q.length > 0) {
    const u = q.shift();
    order.push(u);
    for (const v of adj[u]) {
      if (--indeg[v] === 0) q.push(v);
    }
  }
  return order; // shorter than n means there is a cycle
}

In an interview

LeetCode 207 and 210, Course Schedule: can every course be finished, and in what order?

The red numbers are in-degrees. Add E>A to the example to make a cycle, then watch the sort stop early.

More graphs