每个节点的 DFS 是否会给出有向图中的所有循环
我想找到有向图中的所有循环。从一个节点开始深度优先搜索会找到一些循环（找到后边）。因此，我将 dfs 应用于图中的所有节点（即每次根都是不同的节点）。 我可以使用它获得所有循环（通过消除重复的循环）。但是，我不确定这是否适用于所有图表以及这是否是正确的方法。 谁能建议我这是否适用于所有情况。
谢谢
I want to find all the cycles in a directed graph. Starting Depth-first search from one node will find some cycles(finding back-edges). So, i applied dfs to all the nodes in the graph(i.e. each time the root is a different node).
I am able to get all the cycles using this(by eliminating duplicate ones). But, i am not sure whether this will work for all graphs and whether this is correct approach or not.
Can anyone suggest me whether this works in all situations.
Thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果您有断开连接的节点（图形未连接），那么您将必须从每个节点遍历图形。无论您使用 DFS 还是 BFS 都没有关系，因为您在找到特定节点时不会停止遍历。
我将保留一个全局 VisitedNodes 列表，这样您就不必从已访问过的节点（而不是通常的“每路径”祖先列表）进行完整遍历，以避免循环。
If you have disconnected nodes (the graph is not connected) then you will have to traverse the graph from each node. It won't matter if you use DFS or BFS as you are not stopping your traversal upon finding a particular node.
I would keep a global VisitedNodes list so you don't have to do full traversals from already visited nodes instead of your usual "Per-Path" ancestor list to avoid cycles.
答案是不！因为在所有节点上运行DFS表示多项式时间算法。并且不存在多项式时间算法来查找有向图中的所有循环。
考虑这种情况，假设你有一个包含 n 个节点的完整图（每个节点都指向所有其余节点），那么这 n 个节点的每个非空子集都表示一个循环。这样的子集有 2^n -1 个，因此无法在多项式时间内找到指数周期数。
The answer is NO! Because running DFS on all the nodes indicates a polynomial time algorithm. And there is no polynomial time algorithm exists to find all the cycles in a directed graph.
Consider such case, suppose you have a complete graph with n nodes(every node points to all the rest nodes), then each non-empty subset of this n nodes indicates a cycle. There are 2^n -1 number of such subsets, so no way to find exponential number of cycles in a polynomial time.