伪代码
Coddy 拓扑排序:图算法 课程的第 4 课,共 9 课。
topologicalSort(n, edges):
build directed adjacency; compute indeg[v] for all v
order = []
repeat n times:
pick = smallest v with indeg[v] == 0 (none left -> stop)
mark pick as used (indeg[pick] = -1)
order.add(pick)
for nb in adj[pick]:
indeg[nb] -= 1
return order- indeg[v] 统计入边的数量。只有边
u -> v才会计入indeg[v]。 - 按
0..n-1扫描顶点,并选择入度为 0 的第一个顶点,就能在每一步选出最小的顶点,因此结果是确定的。 - 设置
indeg[pick] = -1是一种简单的标记方式,表示该顶点已经放入结果中。
亲手试试
这节课没有代码挑战。
这节课包含一个小测验。开始学习即可作答,并记录你的进度。
拓扑排序:图算法中的所有课
自己练习: C 在线编译器