Kruskal’s algorithm is a popular algorithm for finding minimum spanning trees. Here is an outline of it:
(1) Start with an empty tree.
(2) Add the shortest edge to the tree.
(3) If it connects two vertices not already connected by previous edges, add the next shortest edge.
(4) Go to (3).
Kruskal’s algorithm is a greedy algorithm. Put simply, a greedy algorithm always does what’s best at that moment. You might think that all algorithms should do that, but sometimes locally optimal decisions don’t lead to global optima. Fortunately, they do in this case.
Like I said in my post on disjoint-set data structures, Kruskal’s algorithm uses a disjoint-set data structure. You assign each vertex a number from 0 to N – 1, where N is the number of vertices. Then you can use subset membership within the disjoint-set…
View original post 31 mots de plus