Minimum Spanning Tree¶

Kruskal (Kruskal)¶

We sort the edges of the graph in ascending order based on their weight. We add the vertices of the graph to the final MST without any edges (assume we are building the MST step by step, and at the beginning, this MST has no edges, and we will add the edges incrementally).

The algorithm starts with the first sorted edge and in each step adds the selected edge to the MST if it does not form a cycle with the previously selected edges. To determine whether the selected edge forms a cycle, we can use DSU.

The proof of correctness for this algorithm is by contradiction. Assume the MST obtained by the algorithm is G, and the true MST is H. Consider the lightest edge used in H but not in G. In Kruskal's algorithm, we must have encountered this edge and skipped it because it would form a cycle. This implies H contains a cycle, which contradicts the assumption that H is an MST.

The time complexity of this algorithm is \(O(m \log n + n)\).

// Assume we are building the MST step by step
struct Edge {
    int u, v, weight;
    bool operator<(Edge const& other) {
        return weight < other.weight;
    }
};

Prim's Algorithm¶

In general, Prim's algorithm maintains a set of vertices, where at each step one vertex is added to the set along with an edge, until finally the vertex set becomes identical to the original graph's vertex set. To better understand this algorithm, carefully observe its steps:

• We create a set representing the vertices present in the MST at each stage of the algorithm.

• We initialize a minimum distance value for all vertices in the graph, setting all values to infinity (a large number) except for an arbitrary starting vertex which is set to zero.

• Until our set matches the graph's vertex set, we repeat these three steps: First, select a vertex u not in our set that has the smallest distance value. Add u to our set, then update the distance values of all neighboring vertices of u. Specifically, if vertex w is connected to u via edge z, and Dis[u] + z is less than Dis[w], we set Dis[w] = Dis[u] + z.

A final note about Prim's algorithm's core idea: At each step, we select the edge with the smallest weight between our chosen vertex set and the remaining vertices in the graph.

Proof of the algorithm: At each step, we select an edge between our set and the remaining vertices. If this edge is not chosen, the MST becomes disconnected (a contradiction). If two edges are chosen, the MST forms a cycle (another contradiction). Thus, exactly one edge must be selected, and to minimize the MST's total weight, the edge with the smallest weight must be chosen—which aligns with the algorithm's behavior.

The complexity of this algorithm is \(O(mlgn + n)\).