How might Union/Find data structures be applied to Kruskal's algorithm?
-
29-09-2019 - |
Question
http://en.wikipedia.org/wiki/Disjoint_sets
http://en.wikipedia.org/wiki/Kruskal's_algorithm
Union/Find data structure being used for disjoint sets...
Solution
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.
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow