algorithm - 图 DFS 检测周期 - (假设)反例

Question

因此 DFS 应该检测有向图中的循环。如果它到达一个之前已经访问过的节点，即它找到一个后边，那么我们就有了一个循环。

我找到了一张图表，我看不出这是怎么回事。我知道我的想法肯定有缺陷，所以如果有人能帮助我，那就太好了。

所以这是带有邻接表的图(绘制它并不完全有效......):

A | B
B | C, D
C | F
D | E
E |
F | E

假设DFS从A开始，到达B时，将C先于D入栈，那么会先到达节点E，然后标记为已访问。然后它会弹出节点C，转到F，然后在F的邻接表中找到E并且E已经被访问过，从而给出一个循环。但是图中确实没有循环。

我推理的缺陷在哪里？

Answer 1

这里的缺陷是在 DFS 期间重新访问节点不一定会提供后退优势。它还可以给出一个交叉边缘或前边缘，这里就是这种情况。仅当您重新访问的节点已开始被探索但尚未处理其所有子节点时，才会出现后退边缘。在这种情况下，由于 E 已经处理了它的所有子级，因此它第二次遇到的边不是后边，因此不应报告任何循环。

希望这对您有所帮助!