algorithm - 如何对深度优先搜索中未遍历的边进行分类？

Question

我有一项作业要求对有向图执行深度优先搜索并对图的所有边进行分类。但是，我对如何对深度优先搜索过程中未遍历的边进行分类感到困惑，因为这些边在搜索过程中是如何分类的。

让我总结一下上图的深度优先搜索。

首先我们从 1 到 2。然后我们从堆栈中弹出 2，因为无处可去，所以我们回到 1。然后我们从 1 到 3。接下来我们从 3 到 4。

好吧，假设我做对了那部分，那么遍历的所有边都是正确的树边？那么，如何对 3 到 2 之间的边和 4 到 3 之间的边进行分类呢？

Answer 1

你的 DFS 应该仍然遍历 3->2 和 4->3 的边。它们分别是交叉边缘和后边缘，IIRC。

您实际上只会在第一次看到节点时将其压入堆栈，但当您访问它时，您会查看其所有传出边，无论它们的目的地是否已被访问。