每个节点的DFS是否会给出有向图中的所有周期

我想查找有向图中的所有周期。从一个节点开始深度优先搜索将找到一些周期（找到后沿）。所以，我将dfs应用于图中的所有节点（即每次根是不同的节点时）。我能够使用这个（通过消除重复的）获得所有的周期。但是，我不确定这是否适用于所有图表，以及这是否正确。任何人都可以告诉我，这是否适用于所有情况。每个节点的DFS是否会给出有向图中的所有周期

由于

来源

2010-06-25 Dileep Reddy

您必须非常小心，因为循环出现在前向，交叉，后退和树边缘的组合中，对于编写处理所有可能性的解决方案来说并不是微不足道的。我一直在寻找这种方法很长时间，最后把它留给了其他解决方案，我已经用php编码了，请点击这里：http://stackoverflow.com/a/9665400/642173 – Melsi 2012-03-18 23:52:43

如果已断开节点（图中未连接），那么你将必须遍历从每个节点的曲线图。使用DFS或BFS并不重要，因为您在查找特定节点时并未停止遍历。

我会保留一个全局VisitedNodes列表，因此您不必从已访问的节点执行完整遍历，而不是通常的“Per-Path”祖先列表以避免循环。

来源

2010-06-25 07:08:42

答案是NO！因为在所有节点上运行DFS指示多项式时间算法。并且没有多项式时间算法存在以找到有向图中的所有周期。考虑这种情况，假设你有一个有n个节点的完整图（每个节点指向所有其余节点），那么这n个节点中的每个非空子集都表示一个周期。有2^n -1个这样的子集，因此无法在多项式时间内找到指数周期数。

来源

2013-04-13 04:11:08 Yuwen

每个节点的DFS是否会给出有向图中的所有周期

回答

相关问题