• Introduction
• Properties of the Minimum Spanning Tree
  • Uniqueness of the Minimum Spanning Tree
  • Maximum Edge Weight in the Minimum Spanning Tree
• Kruskal’s Algorithm for Minimum Spanning Tree
  • Implementation in C++ with DSU
• Time Complexity
• Spanning Tree with Minimum Product
• Maximum Spanning Tree
• Applications of the Algorithm
• Run C Programming Online Compiler

¶Introduction

A Minimum Spanning Tree (MST) is a tree containing subset of the edges of a connected, undirected graph that connects all the vertices without any cycles and with the minimum possible total edge weight. Essentially, it is a tree that spans all the vertices in the graph and has the smallest possible sum of edge weights.
Imagine a telecommunications company wanting to connect several cities with fiber optic cables. The goal is to minimize the total cost of the cables while ensuring that all cities are connected. We can just find the MST of the network to solve this problem problem. MSTs are also crucial in various fields such as network design, including computer, telecommunications, and transportation networks, where minimizing the cost of connecting a set of points is essential.

¶Properties of the Minimum Spanning Tree

¶Uniqueness of the Minimum Spanning Tree

A minimum spanning tree of a graph is unique if the weights of all the edges are distinct. When the edge weights are distinct, there is only one way to connect all the vertices with the minimum possible total edge weight without forming any cycles. However, if there are edges with equal weights, there may be multiple minimum spanning trees for the same graph. Different algorithms or even different runs of the same algorithm might produce different MSTs, but all will have the same total weight.

¶Maximum Edge Weight in the Minimum Spanning Tree

In a minimum spanning tree of a graph, the maximum weight of an edge is the minimum possible from all possible spanning trees of that graph. This property follows from the validity of Kruskal’s algorithm. Kruskal’s algorithm builds the MST by always choosing the smallest available edge that does not form a cycle, ensuring that the largest edge in the resulting MST is as small as possible. Consequently, among all possible spanning trees, the MST will have the smallest possible maximum edge weight.

¶Kruskal’s Algorithm for Minimum Spanning Tree

Kruskal’s algorithm is a greedy algorithm to find the MST of a connected, weighted, undirected graph. It works by sorting all the edges in the graph in non-decreasing order of their weight and then adding edges one by one to the MST, ensuring that no cycles are formed.

• Create a forest where each vertex is a separate tree.
• Sort all the edges in non-decreasing order of their weights.
• Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far using a disjoint-set data structure. If a cycle is not formed, include this edge in the MST. Otherwise, discard it. We can check cycle formation easily using DSU data structure.
• Continue the process for all the remaining edges until we add (V - 1) edges in the MST.

¶Implementation in C++ with DSU

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int u, v, weight;
    bool operator<(Edge const& other) {
        return weight < other.weight;
    }
};

class DSU {
    vector<int> parent, rank;
public:
    DSU(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    int find(int u) {
        if (u != parent[u]) {
            parent[u] = find(parent[u]);
        }
        return parent[u];
    }
    
    void unite(int u, int v) {
        u = find(u);
        v = find(v);
        if (u != v) {
            if (rank[u] < rank[v]) {
                swap(u, v);
            }
            parent[v] = u;
            if (rank[u] == rank[v]) {
                rank[u]++;
            }
        }
    }
};

int main() {
    int n = 4;  // Number of vertices
    vector<Edge> edges = {
        {0, 1, 10},
        {0, 2, 6},
        {0, 3, 5},
        {1, 3, 15},
        {2, 3, 4}
    };

    sort(edges.begin(), edges.end());

    DSU dsu(n);
    int cost = 0;
    vector<Edge> result;

    for (Edge &e : edges) {
        if (dsu.find(e.u) != dsu.find(e.v)) {
            cost += e.weight;
            result.push_back(e);
            dsu.unite(e.u, e.v);
        }
    }

    cout << "Cost of MST: " << cost << endl;
    for (Edge &e : result) {
        cout << e.u << " -- " << e.v << " == " << e.weight << endl;
    }

    return 0;
}

¶Time Complexity

The time complexity of Kruskal’s algorithm primarily depends on the sorting step and the union-find operations.

1. Sorting the Edges: O(E log E) where E is the number of edges.
2. Union-Find Operations: The union and find operations have an almost constant time complexity, O(α(V)), where α( ) is the inverse Ackermann function, which grows very slowly.

Thus, the overall time complexity of Kruskal’s algorithm isO(E log E), since O(E α(V)) is pretty smaller than O(E log E),

¶Spanning Tree with Minimum Product

Given a weighted graph, find the spanning tree that minimizes the product of edge weights.

Solution :

Surprisingly, determining the set of edges that minimizes the total weight of a spanning tree also results in minimizing the product of those edge weights. This connection between addition and multiplication is a fascinating property of minimum spanning trees.

¶Maximum Spanning Tree

Given a weighted graph, find the maximum spanning tree.

Solution :

To find the maximum spanning tree of a graph, a straightforward approach involves transforming the problem into a minimum spanning tree problem. This is achieved by negating the weight of every edge in the graph. Once the weights are inverted, a standard minimum spanning tree algorithm can be applied to determine the maximum spanning tree of the original graph.

¶Applications of the Algorithm

1. Network Design : Used in designing networks such as telecommunication, computer networks, water supply networks, and electrical grids to minimize the cost of connecting various nodes.
2. Civil Engineering : Helps in planning the layout of roads, railways, and pipelines, ensuring minimal construction cost.
3. Computer Graphics : Employed in constructing the mesh of a 3D object by connecting vertices with minimal cost.
4. Electrical Circuits : Designing circuits with minimal wire length.
5. Clustering : Creating clusters of data points by finding the minimum spanning tree of a similarity graph.

¶Run C Programming Online Compiler

To make your learning more effective, exercise the coding examples in the text editor below.

Run C programming online