sorting - 拓扑排序 - 图

Question

如果一个有向图有多个不同的拓扑排序，而且对于每个排序的图，顶点的编号是相同的，所以它的编号必须是第一个或最后一个。是真的还是假的？

标签： sortinggraph

Answer 1

错误。

考虑一个具有4顶点（0-indexed）和以下3边的图。

edges list:
0 2
1 2
2 3

在这里，有两种不同的拓扑排序，即，

Topological Sort 1: 0 1 2 3
Topological Sort 2: 1 0 2 3

但顶点的编号2在它们中是相同的，也不是第一个或最后一个。您可以在此处
可视化上图。确保选择-indexed 和有向图选项。0