T6 拓扑排序序列

• 拓扑排序序列
  • 基于入度的 Kahn 算法
    • 计算所有顶点的入度
    • 使用入度为 0 的顶点加入队列 (如果可选择的顶点多于 1 个，则序列不唯一)
    • 当队列不为空时，弹出一个顶点，将其加入拓扑序列，并将其所有邻接点的入度减 1
  • 基于 DFS 的算法
    • 对每个未访问的顶点执行 DFS，递归地访问其所有邻接顶点。
    • 在递归返回时，将顶点压入栈，最后弹出栈中的顶点即为拓扑排序序列。
      • 如果不压入栈，而是压入队列或直接打印, 则最终序列即为逆拓扑排序序列
    • 如果存在环, 则无法进行拓扑排序。