如何确定图中是否存在闭环路径?

计算科学 图论
2021-12-07 06:27:16

假设我有一个下图中显示的图形的计算机表示:在此处输入图像描述

我怎样才能知道图中是否有一些闭环,比如用红色标记的那个(或更复杂的那个)?换句话说,我需要创建一个算法来检查图中是否存在一些“递归”。我所说的递归是指一个节点将产生结果,这些结果将被作为第一个节点的输入的节点进一步使用。

任何提示、关键词或寻找解决方案的方向将不胜感激。我是这个主题的新手,所以如果需要更多解释,请告诉我。

1个回答

您正在检查此图是否为“有向无环图”,即该图是否包含任何循环。搜索它应该为此提供许多方法。

一种方法是分配权重1到图中的所有节点,并在常规之上使用一个额外的更新n更新 Floyd-Warshall 算法以检测图中是否存在负成本循环。

这是有效的,因为在原始图中有一个循环相当于在原始图中有一个负成本循环1加权图。

如果有n图中的顶点,算法将在Θ(n3)时间和使用Θ(n2)空间。

如果你使用 Python,你可以使用SciPy 中的这个实现并检查它是否会引发“负循环错误”。

另一种更快且空间更小的方法是检查图形上的深度优先搜索是否曾经将您带回您已经看到的节点。如果你有n顶点和m图中的边,这需要Θ(n+m)=O(n2)时间和Θ(n)空间。