CODEWITHSUNDEEP
algorithmgraphcycledisjoint-setsdisjoint-union
Abhishek
Abhishek

Reputation: 462

How to detect a cycle in an Undirected Graph using Disjoint Sets?

Algorithm:

For each edge (u, v) in the Adjacency list:
If u and v do not belong to the same set:
   Union(u, v)
else:
  return true // cycle detected
return false

Graph:

(1)-------(2)

Adjacency List:

[1] -> [2]

[2] -> [1]

Disjoint-Sets:

{{1}, {2}}

Iteration 1:

Edge e = (1, 2)

Union(1, 2)

Disjoint Sets = {{1, 2}}

Iteration 2:

Edge e = (2, 1)

Both 2 and 1 belong to the same set, so the algorithm detects a cycle. It is obvious that the graph does not contain a cycle.

The algorithm works flawlessly for directed graphs. Please help me with this analysis.

Upvotes: 0

Views: 1566

Answers (1)

夢のの夢
夢のの夢

Reputation: 5846

A cycle must have distinct edges! In union find algorithm, you iterate through all the edges. You would need to filter out the duplicate edges from adjacency list. In your case, there is only one iteration so it would return false.

Upvotes: 1

Related Questions