Wasim Thabraze
Wasim Thabraze

Reputation: 810

Kruskal's Algorithm : What is the Algorithm to check if the edges of the graph form a loop or not?

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

Answers (3)

Bartosz Marcinkowski
Bartosz Marcinkowski

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

Vikram Bhat
Vikram Bhat

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.

Union-Find Datastructures

Upvotes: 1

nishant
nishant

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

Related Questions