Define a minimum spanning tree. Write down Kruskal’s algorithm to find minimum…

Concept

For a connected, undirected, weighted graph G = (V, E), a spanning tree connects every vertex, contains exactly |V| - 1 edges, and has no cycle.

A minimum spanning tree (MST) is a spanning tree whose total edge weight is the smallest among all spanning trees. Let A be the selected edges. A cut respects A when no edge of A crosses it. If A is contained in some MST, the cut property says that a minimum-weight edge crossing any cut that respects A is safe: adding it leaves A contained in some MST.

Application: Kruskal’s algorithm

1. List all edges and sort them in non-decreasing order of weight.

2. Create a separate disjoint set for each vertex and initialize the selected-edge set T as empty.

3. Scan the sorted edges. For an edge (u, v), add it to T and union the two sets only when Find(u) and Find(v) are different; otherwise skip it because it would create a cycle.

4. Stop when T contains |V| - 1 edges. If that count cannot be reached, the input graph is disconnected and the procedure produces a minimum spanning forest instead of one spanning tree.

Cross-check

• Every accepted edge joins two different components, so the selected edges remain acyclic. Reaching |V| - 1 accepted edges therefore gives a spanning tree.

• Initially A is empty, so it is contained in every MST. When Kruskal accepts (u, v), let C be the current component containing u. No edge of A crosses (C, V − C), and any lighter crossing edge would already have joined C to the outside; therefore (u, v) is a minimum-weight crossing edge. The cut property preserves the invariant that A is contained in some MST. After |V| − 1 accepted edges, A itself is an MST; equal weights may yield several MSTs.

Result: Kruskal’s algorithm returns an MST in O(E log E) time, dominated by sorting; disjoint-set operations take near-linear additional time.