我想在有向图中找到所有循环。从一个节点开始深度优先搜索会找到一些循环（找到后边）。所以，我将 dfs 应用于图中的所有节点（即每次根是不同的节点）。我可以使用它来获得所有周期（通过消除重复的周期）。但是，我不确定这是否适用于所有图表以及这是否是正确的方法。谁能建议我这是否适用于所有情况。
谢谢
问问题
1218 次
2 回答
0
如果您有断开连接的节点（图表未连接），那么您将不得不从每个节点遍历图表。如果您使用 DFS 或 BFS 并不重要，因为您不会在找到特定节点时停止遍历。
我会保留一个全局 VisitedNodes 列表，这样您就不必从已经访问过的节点而不是您通常的“每路径”祖先列表进行完全遍历以避免循环。
于 2010-06-25T07:08:42.883 回答
0
答案是否定的！因为在所有节点上运行 DFS 表示多项式时间算法。并且不存在多项式时间算法来找到有向图中的所有循环。
考虑这种情况，假设您有一个包含 n 个节点的完整图（每个节点都指向所有其余节点），那么这 n 个节点的每个非空子集都表示一个循环。有 2^n -1 个这样的子集，因此无法在多项式时间内找到指数循环数。
于 2013-04-13T04:11:08.190 回答