graph-algorithm - 拓扑排序基本类比

Question

我最近正在研究 CRLS 的拓扑排序和 DFS。他们有这个进入/退出时间的概念，我们可以通过它将图边分类为

• 树边
• 前缘
• 后缘
• 交叉边缘

所以问题是 - 使用 DFS 的拓扑排序是否会尝试从树中删除前向边，只保留树边以得到排序结果？

标签： graph-algorithmtopological-sort

Answer 1

请注意，如果图有后边，则它不是 DAG（有向无环图），因为它包含一个循环，因此无法进行拓扑排序。

当我们进行拓扑排序时，我们不会删除任何边，我们只是提供一个线性顺序，以便边只在一个方向上传播：从顺序中较早出现的节点到较晚出现的节点。前向边当然是允许存在的就是这样一个命令。您认为下图展示了什么样的拓扑顺序？