Reputation: 810
Can some one provide me the information about how check if the edges of the graph form a loop or not? Any information would be highly helpful. Many thanks in advance.
Upvotes: 2
Views: 8360
Reputation: 6861
The Kruskal algorithm (which you tagged the question with) uses disjoint set data structure initialized with disjoint sets for each vertex. Then, for each edge, two sets that the edge's vertices belong to are merged. If the two vertices are already in the same set, you've found a loop. If you remove the edge every time it happens, you will get a spanning tree. If you sort the edges in order of ascending weight, that would be a minimum spanning tree.
If you need only to know whether a graph contains loops or not, use something simpler as DFS - if any node has an adjacent node (other than parent) which was visited already - you've found a cycle.
Upvotes: 5
Reputation: 6246
It is the use of fast union-find datastructure which check if the edge to be connected is not between vertices that of same cluster.
Upvotes: 1
Reputation: 23
Do a complete DFS on the graph. Maintain two boolean variables, 'visited' and 'completed' for each node in the graph. 'visited' to indicate whether the vertex has been visited or not and 'completed' to indicate whether the DFS starting from that particular node has completed or not. If while doing DFS you hit a node which has already been visited but its DFS has not yet completed, then there exists a cycle in the graph.
Upvotes: 2