CODEWITHSUNDEEP
algorithmdata-structuresgraph-theorydisjoint-sets
question
question

Reputation: 103

How does Union-Find relate or differ to Graphs?

I understand that the former is a data structure while the latter is a mathematical structure.

But when implemented, they seem to share many of the same features and behaviors.

Each element in the disjoint-set can be considered a vertex in a graph. With the edges in the graph representing a set in Union-Find.

After reviewing http://algs4.cs.princeton.edu/15uf/ and http://algs4.cs.princeton.edu/42digraph/

I believe both can answer questions such as:

So is there a greater difference between the two that I'm not seeing? When should I choose to use one over the other?

I see that a graph algorithm can use the Union-Find structure internally http://algs4.cs.princeton.edu/43mst/KruskalMST.java.html

An implementation detail, but if Union-Find is faster, why use Depth-First Search to test for cycles? http://algs4.cs.princeton.edu/44sp/DirectedCycle.java.html

Upvotes: 2

Views: 1376

Answers (1)

Wickoo
Wickoo

Reputation: 7345

Union find is a data structure for dynamic connectivity problems, for example, when you are connecting edges one by one at runtime and want to know if there is a connection. Think of a maze or liquid percolation. Also, in dynamic connectivity problems, you are usually dealing with sets of distinct items. You are essentially building equivalence classes. In many graph problems, however, you are looking for a path, or a connected component.

So to answer your question, if you are dealing with disjoint sets or problems that add/remove edges and want to see when the system is connected or how many connected items are there, use union-find. Otherwise, graph algorithms like DFS/BFS may be faster and easier to implement.

Upvotes: 3

Related Questions