检测是否存在一个循环在无向图中 [英] Detect if there exists a cycle in an undirected graph

问题描述

我的问题是关于检测是否存在一个周期。我不在乎发生的周期，但仅当存在一个周期。 特别是，我工作的一个（最大）生成树算法的实现。我已经按降序排列的边缘，然后我挑选的时候一边，并把它放在集合图中边IFF它不会导致一个循环。

My question is concerned with DETECTING if there exists a cycle. I don't care where the cycle occurs but only if there exist a cycle. In particular, I am working on the implementation of a (maximally) spanning tree algorithm. I have sorted the edges in descending order and then I pick one edge at the time and put it in the set of the graph edges IFF it doesn't cause a cycle.

我还发现，在只够无向图检查 no_of_edges> no_of_vertices - 1 。这是正确的吗？我试图找到一种情况时，这是不正确的BT我不能。当然，这并不意味着，这是正确的。

I have found out that for undirected graphs in only enough to check if no_of_edges > no_of_vertices - 1. Is this right? I am trying to find a case when this is not true bt I cannot. Of course this doesn't imply that this is correct.

感谢

推荐答案

只要运行DFS搜索;它会自动检测到环路，因为这是终止条件为DFS，当你进入一个节点，这是已经在堆栈---你停下来，当你发现一个周期的。

Just run DFS search; it automatically detects loops because that's the stopping condition for DFS --- you stop when you enter a node that's already in a stack, and that's when you have found a cycle.

这篇关于检测是否存在一个循环在无向图中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！