Minimum Spanning Tree Algorithms

Graphs are powerful data structures used to model relationships between entities. A special type of subgraph called a spanning tree is crucial for problems requiring connectivity with minimal redundancy. This module delves into Minimum Spanning Tree (MST) algorithms, focusing on two prominent greedy approaches: Prim's and Kruskal's, which are essential for network design and optimization.

1. Introduction to Graphs and Spanning Trees

A graph $G = (V, E)$ consists of a set of vertices (or nodes) $V$ and a set of edges $E$ connecting pairs of vertices. In a weighted graph, each edge $(u, v) \in E$ has an associated numerical weight $w(u, v)$ , representing a cost, distance, or capacity.

A tree is an undirected graph in which any two vertices are connected by exactly one path, meaning it is connected and acyclic.

A spanning tree of a connected, undirected graph $G$ is a subgraph that is a tree and connects all the vertices of $G$ . Key properties of a spanning tree:

It must be connected.
It must include all $V$ vertices of the original graph.
It must contain exactly $V-1$ edges, where $V$ is the number of vertices.
It must be acyclic.

A Minimum Spanning Tree (MST) for a connected, undirected, weighted graph is a spanning tree whose sum of edge weights is as small as possible. MSTs are fundamental in various applications, such as designing communication networks, routing protocols, and clustering.

Consider a simple graph:

text

      (2)
   A ----- B
  / \     / \
(1) (4) (3) (5)
 /     C     \
E ----- D ----- F
      (6)

A spanning tree would connect all vertices using 5 edges (6-1). An MST would be the one where the sum of weights of these 5 edges is minimal.

2. Properties of Minimum Spanning Trees

Two fundamental properties underpin the correctness of greedy MST algorithms:

2.1. Cut Property

The Cut Property states that for any cut (a partition of the vertices of a connected graph into two non-empty, disjoint sets, say $S$ and $V \setminus S$ ), if an edge $(u, v)$ crosses the cut (i.e., $u \in S$ and $v \in V \setminus S$ ) and has a strictly smaller weight than any other edge crossing the same cut, then this edge must be part of MST of the graph. More generally, minimum-weight edge crossing any cut belongs to MST.

2.2. Cycle Property

The Cycle Property states that for any cycle in a connected, weighted graph, if an edge $(u, v)$ in the cycle has a strictly larger weight than any other edge in that cycle, then $(u, v)$ cannot be part of any MST. If all edges in a cycle have the same weight, then replacing any edge in the cycle with another edge from the cycle would still result in an MST.

3. Prim's Algorithm

Prim's algorithm is a greedy algorithm that builds an MST by starting from an arbitrary vertex and incrementally adding the cheapest available edge that connects a vertex in the growing MST to a vertex outside it, without forming cycles (which is implicitly handled by the "connecting to outside" rule).

Steps:

Initialize an empty MST.
Choose an arbitrary starting vertex and add it to the MST.
Repeat until all vertices are included in the MST:
- Find the edge $(u, v)$ with the minimum weight such that $u$ is in the MST and $v$ is not in the MST.
- Add vertex $v$ and edge $(u, v)$ to the MST.

Example Walkthrough:

Consider the following graph:

text

       (4)
   A ------ B
  / \      / \
(6) (1)  (2) (3)
 /     C     \
E ----- D ----- F
    (5)   (7)

Start at vertex A. MST = . Edges connecting to : (A,C,1), (A,B,4), (A,E,6). Minimum is (A,C,1). Add C and edge (A,C) to MST. MST = .
MST = . Vertices outside: . Edges connecting to : (A,B,4), (A,E,6) (C,B,2), (C,D,3) Minimum among these is (C,B,2). Add B and edge (C,B) to MST. MST = .
MST = . Vertices outside: . Edges connecting to : (A,E,6) (C,D,3) (B,D,7) (Note: original image in source was just 7, I'll assume an edge for D, F for this example) Minimum among these is (C,D,3). Add D and edge (C,D) to MST. MST = .
MST = . Vertices outside: . Edges connecting to : (A,E,6) (D,E,5) (D,F,?) (Assuming an edge (D,F) exists with a weight, let's say 8 for this example) Minimum among these is (D,E,5). Add E and edge (D,E) to MST. MST = .
MST = . Vertices outside: . Edges connecting to : (D,F,8) Minimum is (D,F,8). Add F and edge (D,F) to MST. MST = . All vertices included. The MST edges are (A,C,1), (C,B,2), (C,D,3), (D,E,5), (D,F,8). Total weight: $1+2+3+5+8 = 19$ .

Time Complexity: Using an adjacency list and a min-priority queue (e.g., a Fibonacci heap), Prim's algorithm can achieve a time complexity of $O(E + V \log V)$ , where $V$ is the number of vertices and $E$ is the number of edges. With a binary heap, it's $O(E \log V)$ . For dense graphs (), an adjacency matrix implementation without a priority queue can be .

4. Kruskal's Algorithm

Kruskal's algorithm is another greedy algorithm for finding an MST. It operates by considering edges in non-decreasing order of their weights and adds an edge to the MST if it does not form a cycle with the already selected edges.

Steps:

Initialize an empty MST.
Create a list of all edges in the graph.
Sort the edges in non-decreasing order of their weights.
Initialize a Disjoint Set Union (DSU) data structure where each vertex is in its own set.
Iterate through the sorted edges:
- For each edge $(u, v)$ $(u, v)$ with weight $w$ $w$ :
  - If $u$ $u$ and $v$ $v$ are not already in the same set (i.e., adding this edge does not form a cycle), then:
    - Add the edge $(u, v)$ to the MST.

Example Walkthrough:

Using the same graph as above:

text

       (4)
   A ------ B
  / \      / \
(6) (1)  (2) (3)
 /     C     \
E ----- D ----- F
    (5)   (7)

Edges with weights: (A,C,1), (C,B,2), (C,D,3), (A,B,4), (D,E,5), (A,E,6), (B,D,7), (D,F,8) Sorted edges:

(A,C,1)
(C,B,2)
(C,D,3)
(A,B,4)
(D,E,5)
(A,E,6)
(B,D,7)
(D,F,8)

DSU initially: , , , , ,

Consider (A,C,1): A and C are in different sets. Add (A,C) to MST. Union(A,C). MST = DSU: , , , ,
Consider (C,B,2): C and B are in different sets. Add (C,B) to MST. Union(C,B). MST = DSU: , , ,
Consider (C,D,3): C and D are in different sets. Add (C,D) to MST. Union(C,D). MST = DSU: , ,
Consider (A,B,4): A and B are already in the same set . Adding (A,B) would form a cycle (A-C-B-A). Skip.
Consider (D,E,5): D and E are in different sets. Add (D,E) to MST. Union(D,E). MST = DSU: ,
Consider (A,E,6): A and E are already in the same set. Skip.
Consider (B,D,7): B and D are already in the same set. Skip.
Consider (D,F,8): D and F are in different sets. Add (D,F) to MST. Union(D,F). MST = DSU: All 5 (V-1) edges added. Total weight: $1+2+3+5+8 = 19$ .

Time Complexity: The dominant factor is sorting the edges, which takes $O(E \log E)$ time. DSU operations (Find and Union) with path compression and union by rank/size take nearly constant amortized time, $O(\alpha(V))$ , where $\alpha$ is the inverse Ackermann function, which grows extremely slowly. Thus, the overall complexity is $O(E \log E)$ or (since , ).

Here's a C++ implementation of Kruskal's Algorithm using Disjoint Set Union:

cpp

#include <iostream>
#include <vector>
#include <algorithm> // For std::sort
 
// Structure to represent an edge in the graph
struct Edge {
    int u, v, weight;
 
    // Comparator for sorting edges by weight
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};
 
// Disjoint Set Union (DSU) class
class DSU {
    std::vector<int> parent;
    std::vector<int> rank; // To optimize union operation (union by rank)
public:
    DSU(int n) {
        parent.resize(n + 1);

5. Comparison of Prim's and Kruskal's Algorithms

Both Prim's and Kruskal's algorithms are greedy and correctly find an MST based on the cut property. Their performance characteristics differ based on graph density:

Prim's Algorithm:
- Best for dense graphs: When $E$ is close to $V^2$ , Prim's algorithm with a binary heap (or Fibonacci heap) performs well. Its $O(E \log V)$ or $O(V^2)$ complexity is efficient in these scenarios.

The choice between Prim's and Kruskal's largely depends on the specific characteristics of the input graph.

Summary

A spanning tree is a connected, acyclic subgraph that includes all vertices of a given graph. For a graph with $V$ vertices, a spanning tree always has $V-1$ edges.
A Minimum Spanning Tree (MST) is a spanning tree in a weighted graph with the minimum possible total edge weight.
The Cut Property and Cycle Property are crucial theoretical foundations for greedy MST algorithms.
Prim's Algorithm builds an MST by starting from a single vertex and greedily adding the minimum-weight edge connecting the current MST component to an outside vertex. Its complexity is typically $O(E \log V)$ or $O(V^2)$ , making it efficient for dense graphs.

Assessed progress

Minimum Spanning Tree Algorithms

Minimum Spanning Tree Algorithms

1. Introduction to Graphs and Spanning Trees

2. Properties of Minimum Spanning Trees

2.1. Cut Property

2.2. Cycle Property

3. Prim's Algorithm

4. Kruskal's Algorithm

5. Comparison of Prim's and Kruskal's Algorithms

Summary

Key Concepts

Spanning Tree

Minimum Spanning Tree (MST)

Prim's Algorithm

Kruskal's Algorithm

Cut Property

Quick Check

Advanced Data Structures

Advanced Data Structures