1

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

我发现了一个图表，其中我看不到这是怎么回事。我知道我的思维方式一定有缺陷，所以如果有人能帮助我，那就太好了。

所以这是带有邻接列表的图表（绘制它并不完全有效......）：

一个 | B
B | C, D
C | F
D | E
E |
F | 乙

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

我推理的缺陷在哪里？

4

1 回答 1

2

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

希望这可以帮助！

于 2013-06-08T07:33:40.167 回答