我有一个任务，要求一个人在有向图上执行深度优先搜索，并对图的所有边进行分类 . 但是，我很困惑如何在深度优先搜索过程中对未遍历的边缘进行分类，看看这些边缘在搜索过程中是如何分类的 .
让我总结一下深度优先搜索上图 .
首先我们从1到2.然后我们从堆栈中弹出2，因为无处可去，所以我们回到1.然后我们从1到3.然后我们从3到4 .
好吧，假设我得到了那个部分，那么遍历的所有边都是树边正确吗？那么，如何将边缘分为3到2，边缘从4到3？
您的DFS仍应从3-> 2和4-> 3遍历边缘 . 它们分别是IIRC的交叉边缘和后边缘 .
您第一次看到它时，实际上只会将节点推入堆栈，但是当您访问它时，您会查看其所有传出边缘，无论其目的地是否已被访问过 .
1 回答
您的DFS仍应从3-> 2和4-> 3遍历边缘 . 它们分别是IIRC的交叉边缘和后边缘 .
您第一次看到它时，实际上只会将节点推入堆栈，但是当您访问它时，您会查看其所有传出边缘，无论其目的地是否已被访问过 .