algorithm - 查找图形中的循环数

Question

我必须找出图中的循环数。

我知道 Tarjan 的强连通分量算法，但我有点困惑。

我可以使用 DFS 或 BFS 来查找循环数吗？为什么不能。如果它是树，答案会改变吗

我想问是否每个节点只有一个出边，我可以使用 dfs 吗？

Answer 1

是的，您可以使用 DFS 在图中查找循环。图中存在不同类型的边，包括后边，后边被定义为将顶点连接回图中其先前祖先之一的边。这些是查找已在 DFS 中发现但尚未完成的顶点的边。根据定义，后边意味着一个循环，因此我们可以使用这个定义来计算图中的循环。

执行此操作的简单算法涉及运行 DFS 并跟踪递归堆栈中发现的顶点。因此，每当 DFS 发现一个新顶点时，它就会被标记为“已发现”并放入堆栈中。它将在“完成”后立即从堆栈中取出 - 当顶点的所有子节点都已被发现并且 DFS 已返回到该顶点时。如果稍后在 DFS 中发现未完成并因此位于该堆栈上的已发现顶点，我们知道存在后缘并因此存在循环并且可以将计数器增加 1 或记下它，但您可以选择。

关于这是否随树变化的问题 - 根据定义，树是一种没有循环的数据结构。因此，我们永远不必担心在树中寻找循环。

希望对您有所帮助!