Suggest an edit

Improve this article

Refine the answer for “What is topological sorting in graphs?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## Short answer

Topological sorting is a linear ordering of the vertices of a directed acyclic graph (DAG) in which, for every edge u→v, vertex u comes before vertex v. It exists only for graphs without cycles and is usually built in O(V+E) using Kahn's algorithm (via in-degrees) or a depth-first traversal (DFS).

## Detailed breakdown

### Definition

Topological sorting defines a linear ordering of all vertices of a directed acyclic graph such that every dependency constraint (edge u→v) is respected: u comes before v. The order does not have to be unique, when "independent" vertices are present, several correct sequences are possible.

### When it applies

- Only for directed acyclic graphs (DAG). If a cycle exists, a correct order does not exist.
- To detect a cycle: in Kahn's algorithm, if vertices with a nonzero in-degree remain after processing; in DFS, detecting a back edge (a vertex on the stack/colored gray).

### Key properties

- Correctness: for every edge u→v, vertex u is placed before v.
- Existence: possible only for a DAG; the presence of a cycle makes sorting impossible.
- Non-uniqueness: many valid orders can exist. Uniqueness is achieved if, at every step of Kahn's algorithm, the choice of vertex is unambiguous (the queue always has exactly 1 vertex with zero in-degree). Equivalently, the graph effectively defines an "almost complete" dependency order (a Hamiltonian path exists).
- Complexity: both classical algorithms run in O(V+E) time and O(V+E) memory.

### Algorithms

1. Kahn's algorithm (via in-degrees):
  - Count the in-degree of every vertex.
  - Put all vertices with a zero in-degree into a queue.
  - While the queue is not empty: dequeue a vertex, add it to the answer, "remove" its edges by decreasing the in-degree of its neighbors; those that reach zero in-degree go into the queue.
  - If fewer vertices are processed than exist in the graph, there is a cycle.
2. DFS approach (reverse postorder):
  - Run DFS; add a vertex to the list right before exiting it.
  - After traversing all components of the graph, reverse the list, that is the topological order.
  - Cycle detection: reaching a "gray" vertex (on the recursion stack) means a cycle.

### Example graph and valid orders

Let the vertices be: 0,1,2,3,4. Edges: 0→2, 1→2, 1→3, 3→4. Valid topological orders include, for example: [1,0,3,4,2], [0,1,3,4,2], [1,3,4,0,2]. Note that 0 and 1 are independent of each other and can come in any order before 2.

### Code: Kahn's algorithm (JavaScript)

```
/*
  n - the number of vertices (0..n-1)
  edges - an array of pairs [u, v] for edges u→v
  Returns { order, unique } or throws an error if a cycle exists
*/
function topoSortKahn(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  const indeg = 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 = [];
  let unique = true; // becomes false if at some step there is a choice among more than 1 vertex

while (queue.length) {
    if (queue.length > 1) unique = false;
    // The queue could be sorted for determinism, but that only changes the shape of the order, not correctness
    const u = queue.shift();
    order.push(u);
    for (const v of adj[u]) {
      indeg[v]--;
      if (indeg[v] === 0) queue.push(v);
    }
  }

if (order.length !== n) {
    throw new Error("The graph contains a cycle: topological sorting is impossible");
  }

return { order, unique };
}

// Example usage:
const n = 5;
const edges = [ [0,2], [1,2], [1,3], [3,4] ];
const result = topoSortKahn(n, edges);
console.log(result.order);  // For example: [1,0,3,4,2]
console.log(result.unique); // false, there was a choice at some steps
```

### Code: DFS implementation (Python)

```
from typing import List, Tuple

# n - the number of vertices (0..n-1)
# edges - a list of edges (u, v) for u→v
# Returns a list of vertices in topological order

def topo_sort_dfs(n: int, edges: List[Tuple[int, int]]) -> List[int]:
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)

WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    order = []

def dfs(u: int):
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:
                raise ValueError("The graph contains a cycle: topological sorting is impossible")
            if color[v] == WHITE:
                dfs(v)
        color[u] = BLACK
        order.append(u)  # reverse postorder

for u in range(n):
        if color[u] == WHITE:
            dfs(u)

order.reverse()
    return order

# Example usage
n = 5
edges = [(0, 2), (1, 2), (1, 3), (3, 4)]
print(topo_sort_dfs(n, edges))  # For example: [1, 0, 3, 4, 2]
```

### Checking order uniqueness

During Kahn's algorithm, watch the size of the queue: if at any point it contains more than one vertex with a zero in-degree, uniqueness does not hold. If exactly one vertex appears at every step, the order is unique.

### Applications

- Scheduling tasks with dependencies (CI/CD pipelines, step orchestration).
- Building projects and module systems (determining compile/link order).
- Resolving package dependencies, loading modules/database migrations in the correct order.
- Courses with prerequisites; computing the order in which to take them.

### Frequent mistakes

- Applying it to a graph with cycles, you must either remove the cycle or signal an error.
- In DFS, adding a vertex before traversing its children, it is correct to add it after the traversal (postorder) and then reverse.
- Forgetting to handle isolated vertices (with no edges), they must still appear in the order.
- Misinterpreting edge direction (swapping the dependency and the dependent node).
- Expecting a single result where the graph allows several correct orders.

### Complexity

Both Kahn's algorithm and the DFS variant run in O(V+E) time; in memory they store the graph and additional structures (in-degrees/colors, queue/stack), which also fits in O(V+E).

Markdown · drag & drop images · ⌘B / ⌘I shortcuts972 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.