Menu
CoddyTech

伪代码

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 是一种简单的标记方式,表示该顶点已经放入结果中。

亲手试试

这节课没有代码挑战。

quiz icon自我测试

这节课包含一个小测验。开始学习即可作答,并记录你的进度。

拓扑排序:图算法中的所有课

自己练习: C 在线编译器