拓扑排序模板

一句话说明

Kahn 模板的本质就是不断取出入度为 0 的点；如果最后没取完，图里一定有环。

模板适用场景

• 课程依赖
• 任务依赖
• DAG 排序
• 判定有向图是否有环

Go 模板：Kahn

func TopologicalSort(nodeCount int, edges [][2]int) []int {
    graph := make([][]int, nodeCount)
    indegree := make([]int, nodeCount)
 
    for _, e := range edges {
        from, to := e[0], e[1]
        graph[from] = append(graph[from], to)
        indegree[to]++
    }
 
    queue := []int{}
    for i := 0; i < nodeCount; i++ {
        if indegree[i] == 0 {
            queue = append(queue, i)
        }
    }
 
    order := []int{}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        order = append(order, node)
 
        for _, next := range graph[node] {
            indegree[next]--
            if indegree[next] == 0 {
                queue = append(queue, next)
            }
        }
    }
 
    if len(order) != nodeCount {
        return nil
    }
    return order
}

为什么它能判环

因为只有“所有前驱都处理完”的点，才能入队。
如果最后还有点永远入不了队，就说明它们互相卡住了，也就是存在有向环。

如果要求字典序最小

把普通队列改成最小堆即可。
核心逻辑不变，只是每次优先取当前最小编号的入度 0 节点。

易错点

拓扑排序模板最容易错的地方

• 拓扑排序只适用于有向图。
• 结果长度小于点数，返回空结果或 nil，表示图中有环。
• 重边是否允许，要看题目输入约定；如果有重边，入度也要对应多次增加。

复杂度

指标	复杂度
时间复杂度	O(V + E)
空间复杂度	O(V + E)

相关主题

• 图算法
• DFS与BFS

---

返回：算法模板