Trees · Minimum Spanning Tree
Lesson 2
In the problem above, we are given a connected weighted graph, and we now want to find not just any spanning tree, but the minimum one.
There is a natural greedy algorithm for finding the minimum spanning tree:
We will iterate through the edges in increasing order of weight. We take each edge if it does not create a cycle.It is known as Kruskal's algorithm. Its correctness follows from the following important cut property.
