拓扑排序

图

说明

反复取入度为零的节点；仅有向无环图能输出全部节点。

分析

先统计每个节点的入度，把所有入度为零的节点放入队列。移除节点时减少其后继的入度，新变成零的节点即可入队。

图解推演

图 0→1、0→2、1→2 的入度为 [0,1,2]。移除 0 后变成 [0,0,1]，此时只能加入 1；再移除 1 才能加入 2。入度为零表示所有前置依赖都已完成；多个零入度点可有多种合法顺序，不应把输出唯一性当成正确性要求。

查看图表代码

适用前提与边界

若结果数量小于顶点数，剩余节点属于有向环或依赖于环，无法给出完整顺序。

示例输入与调用

fmt.Println(TopologicalSort([][]int{{1, 2}, {2}, {}}))

运行输出

[0 1 2]

完整 Go 示例

package main

import "fmt"

func TopologicalSort(g [][]int) []int {
	indeg := make([]int, len(g))
	for _, edges := range g {
		for _, v := range edges {
			indeg[v]++
		}
	}
	q := []int{}
	for v, d := range indeg {
		if d == 0 {
			q = append(q, v)
		}
	}
	out := []int{}
	for h := 0; h < len(q); h++ {
		v := q[h]
		out = append(out, v)
		for _, w := range g[v] {
			indeg[w]--
			if indeg[w] == 0 {
				q = append(q, w)
			}
		}
	}
	return out
}

func main() {
	fmt.Println(TopologicalSort([][]int{{1, 2}, {2}, {}}))
}