Devoted
Reputation: 183403
How might Union/Find data structures be applied to Kruskal's algorithm?
http://en.wikipedia.org/wiki/Disjoint_sets
http://en.wikipedia.org/wiki/Kruskal's_algorithm
Union/Find data structure being used for disjoint sets...
Upvotes: 0
Views: 1369
Answers (1)
lijie
Reputation: 4871
It is stated in the entry for Kruskal's algorithm, but you can use the union/find structure to test (via FIND) if the edge connects two different trees or whether it will form a cycle when added.
The same structure can be updated (via UNION) if the edge does not form a cycle and is added to the spanning tree.
Upvotes: 2
Related Questions
- Kruskal's MST : Union operation using Union-Find DS: Guarantee on join taking place between the nodes with least edge weight
- Quick-Find Union on N Elements
- how to make sets and solve unions in disjoint set data structures?
- Do I have to use a Union Find data structure when implementing Kruskal's algoithm?
- how does kruskal's algorithm's performance gets affected by the disjoint set data structure?
- Java structure for set of sets that have to union? (for Kruskal's Algorithm)
- Does using union-find in Kruskal's algorithm actually affect worst-case runtime?
- In search of the proper Union DST with inverse-ackermann complexity
- Kruskal's algorithm and disjoint-set data structure: Do I need the following two lines of code?
- Union/find algorithm without union by rank for disjoint-set forests data structure