如何确定图中是否存在闭环路径?
计算科学
图论
2021-12-07 06:27:16
1个回答
您正在检查此图是否为“有向无环图”,即该图是否包含任何循环。搜索它应该为此提供许多方法。
一种方法是分配权重到图中的所有节点,并在常规之上使用一个额外的更新更新 Floyd-Warshall 算法以检测图中是否存在负成本循环。
这是有效的,因为在原始图中有一个循环相当于在原始图中有一个负成本循环加权图。
如果有图中的顶点,算法将在时间和使用空间。
如果你使用 Python,你可以使用SciPy 中的这个实现并检查它是否会引发“负循环错误”。
另一种更快且空间更小的方法是检查图形上的深度优先搜索是否曾经将您带回您已经看到的节点。如果你有顶点和图中的边,这需要时间和空间。
其它你可能感兴趣的问题