c# - 困惑如何在有死胡同的无向图中找到循环

Question

我一直在考虑如何在我的图表数据中找到一个循环，但我有点迷失了如何跟踪我在图表上的行进位置以及当我发现死胡同时如何回溯。

这是一个视觉示例：

我可以通过跟随路径轻松找到这里的循环，直到我回到 0 - 问题出在节点 3，我必须检查节点 4 和 5。

很明显，4->5 将是一个死胡同，不会成为循环的一部分，但是你如何编写代码来回溯到节点 3 以继续到节点 6？

标签： c#graph-theory

Answer 1

作为深度优先搜索的一部分，您可以将节点存储在“已访问”集中

当您转到新节点时，请在检查后添加到集合中visited.Contains()。如果为真，你有一个循环（多次回到同一个节点）

因此，从逻辑上讲，假设您从 3 开始（或到达它），并且边缘是随机挑选的，因为它们不是定向的

(program-start) visited = {}

at = 3, visited={3}
at = 4, visited={3, 4}
at = 5, visited={3, 4, 5}

在这里，你必须从 5 中选择唯一的边来遍历，将你送回 4，然后检查你的集合，它已经在那里了......