拓扑排序

拓扑排序

• 只存在于有向无环图（DAG）中

• 该序列必须满足

  1. 每个顶点出现且只出现一次。
  2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

• 实现

  1. 寻找一个入度为0的顶点并输出
  2. 删除该点，并删除所有以该点为起点的有向边（即将该点连接的所有点入度减一）
  3. 重复1和2，直到图为空为止

• 代码

  for(int i = 0;i