How to Perform Topological Sorting on a Directed Acyclic Graph (DAG): DFS vs BFS Methods

Topological sorting orders the vertices of a directed acyclic graph so that every edge u → v appears with u before v, typically implemented via DFS post-order reversal or Kahn’s BFS algorithm with indegree tracking.

Topological sorting is essential for scheduling tasks with dependencies, compiling code, and resolving package installation orders. The labuladong/fucking-algorithm repository provides complete implementations of both DFS-based and BFS-based approaches in 数据结构系列/拓扑排序.md, demonstrating how to detect cycles while generating the linear ordering.

What Is Topological Sorting on a Directed Acyclic Graph?

A topological sort of a directed acyclic graph (DAG) is a linear ordering of its vertices such that for every directed edge from vertex u to vertex v, u comes before v in the ordering. This is only possible if the graph contains no cycles—hence the requirement for the graph to be a DAG.

If the graph contains a cycle, no valid ordering exists because you would need a vertex to appear before itself. Therefore, any topological sorting algorithm must first perform cycle detection.

DFS-Based Topological Sort (Post-Order Reversal)

The DFS-based approach leverages depth-first search to record vertices in post-order, then reverses the result to obtain the topological order.

Algorithm Logic and Cycle Detection

In 数据结构系列/拓扑排序.md, the DFS implementation uses three states to track vertices:

• visited: Marks vertices that have been fully processed
• onPath: Tracks the current recursion stack to detect back-edges (cycles)
• Post-order recording: Vertices are appended to the result list after all descendants are processed

The algorithm works because a vertex is added to the order only after all vertices it depends on (its outgoing neighbors) have been processed. Reversing this post-order list places independent vertices before dependent ones.

Implementation in Go

The following Go function from the repository implements the DFS-based approach with cycle detection:

func topologicalSortDFS(g [][]int) ([]int, bool) {
    n := len(g)
    onPath := make([]bool, n)   // marks recursion stack
    visited := make([]bool, n)
    order := []int{}
    var dfs func(v int) bool
    dfs = func(v int) bool {
        if onPath[v] { return false }      // cycle detected
        if visited[v] { return true }
        onPath[v], visited[v] = true, true
        for _, to := range g[v] {
            if !dfs(to) { return false }
        }
        onPath[v] = false
        order = append(order, v) // post-order
        return true
    }
    for i := 0; i < n; i++ {
        if !visited[i] && !dfs(i) { return nil, false }
    }
    // reverse post-order -> topological order
    for i, j := 0, len(order)-1; i < j; i, j = i+1, j-1 {
        order[i], order[j] = order[j], order[i]
    }
    return order, true
}

(Source: 数据结构系列/拓扑排序.md, lines 256-327)

BFS-Based Topological Sort (Kahn’s Algorithm)

Kahn’s algorithm uses breadth-first search and indegree tracking to iteratively remove vertices with no incoming edges.

Indegree Tracking and Queue Processing

As documented in 数据结构系列/拓扑排序.md, Kahn’s algorithm follows these steps:

1. Calculate indegrees: Count incoming edges for every vertex
2. Initialize queue: Enqueue all vertices with indegree 0 (no dependencies)
3. Process queue: Remove a vertex, append it to the result, and decrement indegrees of its neighbors
4. Enqueue neighbors: When a neighbor’s indegree reaches 0, enqueue it

If the result list contains all vertices, the graph is a DAG and the list is a valid topological order. If fewer vertices are processed than exist in the graph, a cycle is present.

Implementation in Go

The BFS implementation from the repository uses a slice as a queue:

func topologicalSortBFS(g [][]int) ([]int, bool) {
    n := len(g)
    indeg := make([]int, n)
    for v := 0; v < n; v++ {
        for _, to := range g[v] {
            indeg[to]++
        }
    }
    queue := []int{}
    for i := 0; i < n; i++ {
        if indeg[i] == 0 { queue = append(queue, i) }
    }
    order := []int{}
    for len(queue) > 0 {
        v := queue[0]
        queue = queue[1:]
        order = append(order, v)
        for _, to := range g[v] {
            indeg[to]--
            if indeg[to] == 0 {
                queue = append(queue, to)
            }
        }
    }
    if len(order) != n { return nil, false } // cycle exists
    return order, true
}

(Source: 数据结构系列/拓扑排序.md, lines 534-586)

Comparing DFS and BFS Approaches

Both methods correctly compute topological orderings when the input is a DAG, but they differ in implementation details and use cases:

• DFS approach: Naturally combines cycle detection with ordering using recursion stack tracking (onPath array). It produces a valid ordering by recording vertices in post-order and reversing. This method is often more intuitive for problems requiring explicit dependency chains.

• BFS approach (Kahn’s): Uses indegree counting and a queue, making it iterative and sometimes easier to implement without recursion depth concerns. It naturally identifies all vertices with no dependencies at each step, which is useful for parallel processing or when you need to know which tasks are "ready" at any given moment.

According to the source code in labuladong/fucking-algorithm, both implementations first verify the graph is acyclic before returning an ordering. The DFS version detects cycles via the onPath boolean array, while the BFS version checks if the final order length equals the total vertex count.

Summary

• Topological sorting linearizes a DAG so that every directed edge u → v respects the u-before-v ordering.
• DFS method: Uses post-order traversal and reversal, detecting cycles via a recursion stack (onPath array) as shown in 数据结构系列/拓扑排序.md.
• BFS method (Kahn’s): Uses indegree tracking and a queue to iteratively remove vertices with no incoming edges, verifying completeness to detect cycles.
• Both approaches require O(V + E) time and O(V) space, where V is the number of vertices and E is the number of edges.
• The repository labuladong/fucking-algorithm provides reference implementations in Go, C++, Java, and Python in 多语言解法代码/solution_code.md.

Frequently Asked Questions

What happens if the graph contains a cycle?

If the graph contains a cycle, no valid topological ordering exists because a vertex would need to appear before itself. The DFS implementation in 数据结构系列/拓扑排序.md detects this via the onPath array—returning false when it encounters a back-edge. The BFS implementation detects cycles by checking if the number of processed vertices equals the total vertex count; if fewer vertices are processed, a cycle exists.

Can topological sorting produce multiple valid orderings?

Yes, a DAG can have multiple valid topological orderings. When several vertices have zero indegree (or no unvisited dependencies in DFS), you can choose any of them as the next vertex in the sequence. Both the DFS and BFS implementations naturally produce one valid ordering, but the specific order depends on traversal choices (e.g., which neighbor is visited first or which zero-indegree vertex is dequeued first).

Which algorithm is faster for large sparse graphs?

Both DFS and BFS topological sorting run in O(V + E) time, making them equally efficient asymptotically. However, for very large sparse graphs, the BFS approach (Kahn’s algorithm) may have practical advantages because it uses an explicit queue and avoids recursion depth limits that could cause stack overflow in deep graphs. The DFS approach, however, often has better cache locality for dense graphs.

How do I implement topological sorting in Python or Java?

The labuladong/fucking-algorithm repository provides multi-language implementations in 多语言解法代码/solution_code.md. The logic remains identical to the Go examples: for DFS, use a recursion stack set and post-order list; for BFS, use an indegree map/array and a queue. Python implementations typically use collections.deque for the BFS queue, while Java implementations use ArrayDeque and HashMap or arrays for indegree tracking.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}