Mastering the Minimum Spanning Tree: A Deep Dive

A Minimum Spanning Tree (MST) is a fundamental concept in graph theory that applies to connected, undirected graphs. In simple terms, a spanning tree of a graph is a subgraph that connects all the vertices together without forming any cycles, and a minimum spanning tree is a spanning tree that has the minimum possible total edge weight.

What is a Spanning Tree?

Imagine a network of cities connected by roads, where each road has a certain length (or cost). The objective is to connect all the cities with a subset of these roads such that the total length (or cost) is minimized, and there are no redundant paths forming loops. This network would be the spanning tree, and if you ensure that the total length is as small as possible, it becomes a minimum spanning tree.

In mathematical terms, for a graph G(V,E), where V is the set of vertices and E is the set of edges, a spanning tree is a subgraph that includes all the vertices (V) and (V−1) edges from E without any cycles. The minimum spanning tree is the spanning tree with the smallest sum of edge weights.

Why is MST Important?

The MST problem arises in many practical scenarios where we need to optimize the construction or connection of networks while minimizing costs. Some real-world examples include:

• Network design: Constructing efficient telecommunications, electrical, or computer networks with minimal wiring or cost.
• Transportation networks: Planning road, railway, or pipeline connections between cities or industrial hubs.
• Clustering in machine learning: Grouping data points by minimizing inter-cluster distances.

An important aspect of MST is that it guarantees a globally optimal solution using a greedy approach. In other words, starting with the lowest-cost options and progressively building the tree ensures that the total cost is minimized while keeping the network connected.

A Minimum Spanning Tree (MST) possesses several important properties that define its structure and usage in optimization problems. Here are some of the key properties of an MST:

1. Connected and Undirected Graph
• The graph for which we can find an MST must be both connected and undirected. A connected graph means there is a path between every pair of vertices. In an undirected graph, edges do not have a direction, meaning the connection between two vertices is bidirectional.
  
  
2. Contains (V−1) Edges
• For a graph with V vertices, the MST will always have exactly (V−1) edges. This is because an MST is a tree, and in a tree, the number of edges is always one less than the number of vertices.
  
  
• Having any more than (V−1) edges would result in cycles, and any fewer would mean the graph is not fully connected.
  
  
3. No Cycles
• A spanning tree, by definition, does not contain any cycles. An MST, being a type of spanning tree, also adheres to this rule. If a cycle were to exist, one could remove an edge from the cycle to reduce the total weight of the spanning tree.
  
  
4. Unique Weights Produce a Unique MST
• If all edge weights in the graph are unique, the MST will also be unique. This is because there can be only one way to connect all the vertices with the minimum possible total edge weight when no two edges have the same weight.
  
  
• However, if there are edges with the same weight, there can be multiple MSTs.
  
  
5. MST Minimizes Total Edge Weight
• The primary characteristic of an MST is that it minimizes the total weight of the edges used in the spanning tree. No other spanning tree of the same graph can have a lower sum of edge weights.
  
  
• This makes MSTs ideal for applications where minimizing cost, length, or another factor associated with edge weights is important.
  
  
6. Subgraph of the Original Graph
• An MST is always a subgraph of the original graph, meaning that it is derived from the original graph by removing some edges while retaining all the vertices. The MST includes only those edges necessary to maintain connectivity and minimize weight.
  
  
7. Cut Property
• The cut property states that for any cut (a way of dividing the graph's vertices into two disjoint sets), the minimum weight edge that crosses the cut and connects the two sets must be part of the MST.
  
  
• This property is fundamental to greedy MST algorithms, such as Kruskal’s and Prim’s, where selecting the smallest edge crossing a cut helps build the MST step by step.
  
  
8. Greedy Algorithms Can Find MST
• The structure of MSTs allows greedy algorithms to find the optimal solution. Both Kruskal’s and Prim’s algorithms use a greedy approach to incrementally build the MST, ensuring that the minimal total edge weight is achieved.
  
  
9. Removing an Edge Increases the Weight
• If you remove an edge from an MST, the graph will no longer be connected. To reconnect the graph, you must add another edge, but this new edge will have a weight greater than or equal to the one removed, increasing the total weight.
  
  
10. Spanning Tree with Minimum Weight

• The MST ensures that all vertices are connected, and out of all the possible spanning trees that can be formed from the graph, the MST is the one with the minimum total weight of edges.

Note:

In the case of a connected graph with several possible spanning trees, the MST will always have the lowest possible total edge weight, but it’s important to note that if the graph has multiple edges with the same weight, multiple MSTs can exist.

There are two widely used greedy algorithms to find the Minimum Spanning Tree (MST) in a graph: Kruskal’s Algorithm and Prim’s Algorithm. Both algorithms efficiently find the MST but use different approaches to achieve this. Let's explore each one in detail.

1. Kruskal’s Algorithm

Given a weighted, undirected, and connected graph of V vertices and E edges. The task is to find the sum of weights of the edges of the Minimum Spanning Tree.

Example :

Input Format:

V = 5, edges = { {0, 1, 2}, {0, 3, 6}, {1, 2, 3}, {1, 3, 8}, {1, 4, 5}, {4, 2, 7}}

Result: 16

Explanation: The minimum spanning tree for the given graph is drawn below:

MST = {(0, 1), (0, 3), (1, 2), (1, 4)}

How Kruskal's Algorithm Works:

We will be implementing Kruskal’s algorithm using the Disjoint Set data structure that we have previously learned.

Now, we know Disjoint Set provides two methods named findUPar()(This function helps to find the ultimate parent of a particular node) and Union(This basically helps to add the edges between two nodes). To know more about these functionalities, do refer to the article on Disjoint Set.

The algorithm steps are as follows:

• First, we need to extract the edge information(if not given already) from the given adjacency list in the format of (wt, u, v) where u is the current node, v is the adjacent node and wt is the weight of the edge between node u and v and we will store the tuples in an array.
  
  
• Then the array must be sorted in the ascending order of the weights so that while iterating we can get the edges with the minimum weights first.
  
  

After that, we will iterate over the edge information, and for each tuple, we will apply the following operation:

• First, we will take the two nodes u and v from the tuple and check if the ultimate parents of both nodes are the same or not using the findUPar() function provided by the Disjoint Set data structure.
  
  
• If the ultimate parents are the same, we need not do anything to that edge as there already exists a path between the nodes and we will continue to the next tuple.
  
  
• If the ultimate parents are different, we will add the weight of the edge to our final answer(i.e. mstWt variable used in the following code) and apply the union operation(i.e. either unionBySize(u, v) or unionByRank(u, v)) with the nodes u and v. The union operation is also provided by the Disjoint Set.

Finally, we will get our answer (in the mstWt variable as used in the following code) successfully.

Note: Points to remember if the graph is given as an adjacency list we must extract the edge information first. As the graph contains bidirectional edges we can get a single edge twice in our array (For example, (wt, u, v) and (wt, v, u), (5, 1, 2) and (5, 2, 1)). But we should not worry about that as the Disjoint Set data structure will automatically discard the duplicate one.

Note: This algorithm mainly contains the Disjoint Set data structure used to find the minimum spanning tree of a given graph. So, we just need to know the data structure.

#include <bits/stdc++.h>

using namespace std;

class DisjointSet {

  vector < int > rank, parent, size;

  public:

    DisjointSet(int n) {

      rank.resize(n + 1, 0);

      parent.resize(n + 1);

      size.resize(n + 1);

      for (int i = 0; i <= n; i++) {

        parent[i] = i;

        size[i] = 1;

      }

    }

  int findUPar(int node) {

    if (node == parent[node])

      return node;

    return parent[node] = findUPar(parent[node]);

  }

  void unionByRank(int u, int v) {

    int ulp_u = findUPar(u);

    int ulp_v = findUPar(v);

    if (ulp_u == ulp_v) return;

    if (rank[ulp_u] < rank[ulp_v]) {

      parent[ulp_u] = ulp_v;

    } else if (rank[ulp_v] < rank[ulp_u]) {

      parent[ulp_v] = ulp_u;

    } else {

      parent[ulp_v] = ulp_u;

      rank[ulp_u]++;

    }

  }

  void unionBySize(int u, int v) {

    int ulp_u = findUPar(u);

    int ulp_v = findUPar(v);

    if (ulp_u == ulp_v) return;

    if (size[ulp_u] < size[ulp_v]) {

      parent[ulp_u] = ulp_v;

      size[ulp_v] += size[ulp_u];

    } else {

      parent[ulp_v] = ulp_u;

      size[ulp_u] += size[ulp_v];

    }

  }

};

class Solution

{

  public:

    //Function to find sum of weights of edges of the Minimum Spanning Tree
    int spanningTree(int V, vector < vector < int >> adj[])

  {

    // 1 - 2 wt = 5

    /// 1 -> (2, 5)

    // 2 -> (1, 5)

    // 5, 1, 2

    // 5, 2, 1

    vector < pair < int,
    pair < int,
    int >>> edges;

    for (int i = 0; i < V; i++) {

      for (auto it: adj[i]) {

        int adjNode = it[0];

        int wt = it[1];

        int node = i;

        edges.push_back({
          wt,
          {
            node,
            adjNode
          }
        });

      }

    }

    DisjointSet ds(V);

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

    int mstWt = 0;

    for (auto it: edges) {

      int wt = it.first;

      int u = it.second.first;

      int v = it.second.second;

      if (ds.findUPar(u) != ds.findUPar(v)) {

        mstWt += wt;

        ds.unionBySize(u, v);

      }

    }

    return mstWt;

  }

};

int main() {

  int V = 5;

  vector<vector<int>> edges = {{0, 1, 2}, {0, 2, 1}, {1, 2, 1}, {2, 3, 2}, {3, 4, 1}, {4, 2, 2}};

  vector < vector < int >> adj[V];

  for (auto it: edges) {

    vector < int > tmp(2);

    tmp[0] = it[1];

    tmp[1] = it[2];

    adj[it[0]].push_back(tmp);

    tmp[0] = it[0];

    tmp[1] = it[2];

    adj[it[1]].push_back(tmp);

  }

  Solution obj;

  int mstWt = obj.spanningTree(V, adj);

  cout << "The sum of all the edge weights: " << mstWt << endl;

  return 0;

}

Time Complexity:

O(N+E) + O(E logE) + O(E*4α*2) where N = no. of nodes and E = no. of edges. O(N+E) for extracting edge information from the adjacency list. O(E logE) for sorting the array consists of the edge tuples. Finally, we are using the disjoint set operations inside a loop. The loop will continue to E times. Inside that loop, there are two disjoint set operations like findUPar() and UnionBySize() each taking 4 and so it will result in 4*2. That is why the last term O(E*4*2) is added.

Given a weighted, undirected, and connected graph of V vertices and E edges. The task is to find the sum of weights of the edges of the Minimum Spanning Tree.
(Sometimes it may be asked to find the MST as well, where in the MST the edge-informations will be stored in the form {u, v}(u = starting node, v = ending node).)

How Prim's Algorithm Works:

In order to implement Prim’s algorithm, we will be requiring an array(visited array) and a priority queue that will essentially represent a min-heap. We need another array(MST) as well if we wish to store the edge information of the minimum spanning tree.

The algorithm steps are as follows:

Priority Queue(Min Heap): The priority queue will be storing the pairs (edge weight, node). We can start from any given node. Here we are going to start from node 0 and so we will initialize the priority queue with (0, 0). If we wish to store the mst of the graph, the priority queue should instead store the triplets (edge weight, adjacent node, parent node) and in that case, we will initialize with (0, 0, -1).

Visited array: All the nodes will be initially marked as unvisited.

Sum variable: It will be initialized with 0 and we wish that it will store the sum of the edge weights finally.

MST array(optional): If we wish to store the minimum spanning tree(MST) of the graph, we need this array. This will store the edge information as a pair of starting and ending nodes of a particular edge.

• We will first push edge weight 0, node value 0, and parent -1 as a triplet into the priority queue to start the algorithm.

Note: We can start from any node of our choice. Here we have chosen node 0.

• Then the top-most element (element with minimum edge weight as it is the min-heap we are using) of the priority queue is popped out.
  
  
• After that, we will check whether the popped-out node is visited or not.
  
  
• If the node is visited: We will continue to the next element of the priority queue.
  
  
• If the node is not visited: We will mark the node visited in the visited array and add the edge weight to the sum variable. If we wish to store the mst, we should insert the parent node and the current node into the mst array as a pair in this step.
  
  
• Now, we will iterate on all the unvisited adjacent nodes of the current node and will store each of their information in the specified triplet format i.e. (edge weight, node value, and parent node) in the priority queue.
  
  
• We will repeat steps 2, 3, and 4 using a loop until the priority queue becomes empty.
  
  
• Finally, the sum variable should store the sum of all the edge weights of the minimum spanning tree.

Note: Points to remember if we do not wish to store the mst(minimum spanning tree) for the graph and are only concerned about the sum of all the edge weights of the minimum spanning tree:

• First of all, we will not use the triplet format instead, we will just use the pair in the format of (edge weight, node value). Basically, we do not need the parent node.
  
  
• In step 3, we need not store anything in the mst array and we need not even use the mst array in our whole algorithm as well.

Example :

Input Format:

V = 5, edges = { {0, 1, 2}, {0, 3, 6}, {1, 2, 3}, {1, 3, 8}, {1, 4, 5}, {4, 2, 7}}

Result: 16

Explanation:

The minimum spanning tree for the given graph is drawn below:

MST = {(0, 1), (0, 3), (1, 2), (1, 4)}

#include <bits/stdc++.h>

using namespace std;
class Solution {
  public:
    //Function to find sum of weights of edges of the Minimum Spanning Tree.
    int spanningTree(int V, vector < vector < int >> adj[]) {
      priority_queue < pair < int, int > ,
        vector < pair < int, int > > , greater < pair < int, int >>> pq;
      vector < int > vis(V, 0);
      // {wt, node}
      pq.push({
        0,
        0
      });
      int sum = 0;
      while (!pq.empty()) {
        auto it = pq.top();
        pq.pop();
        int node = it.second;
        int wt = it.first;
        if (vis[node] == 1) continue;
        // add it to the mst
        vis[node] = 1;
        sum += wt;
        for (auto it: adj[node]) {
          int adjNode = it[0];
          int edW = it[1];
          if (!vis[adjNode]) {
            pq.push({
              edW,
              adjNode
            });
          }
        }
      }
      return sum;
    }
};
int main() {
  int V = 5;
  	vector<vector<int>> edges = {{0, 1, 2}, {0, 2, 1}, {1, 2, 1}, {2, 3, 2}, {3, 4, 1}, {4, 2, 2}};
  vector < vector < int >> adj[V];
  for (auto it: edges) {
    vector < int > tmp(2);
    tmp[0] = it[1];
    tmp[1] = it[2];
    adj[it[0]].push_back(tmp);
    tmp[0] = it[0];
    tmp[1] = it[2];
    adj[it[1]].push_back(tmp);
  }
  Solution obj;
  int sum = obj.spanningTree(V, adj);
  cout << "The sum of all the edge weights: " << sum << endl;
  return 0;
}

Intuition:

The intuition of this algorithm is the greedy technique used for every node. If we carefully observe, for every node, we are greedily selecting its unvisited adjacent node with the minimum edge weight(as the priority queue here is a min-heap and the topmost element is the node with the minimum edge weight). Doing so for every node, we can get the sum of all the edge weights of the minimum spanning tree and the spanning tree itself(if we wish to) as well.

Time Complexity:

O(E*logE) + O(E*logE)~ O(E*logE), where E = no. of given edges.The maximum size of the priority queue can be E so after at most E iterations the priority queue will be empty and the loop will end. Inside the loop, there is a pop operation that will take logE time. This will result in the first O(E*logE) time complexity. Now, inside that loop, for every node, we need to traverse all its adjacent nodes where the number of nodes can be at most E. If we find any node unvisited, we will perform a push operation and for that, we need a logE time complexity. So this will result in the second O(E*logE).

The Minimum Spanning Tree (MST) is a powerful concept in graph theory, with wide-ranging applications in real-world optimization problems. From designing cost-effective networks like electrical grids and telecommunication systems to minimizing distances in transportation networks, MST helps find the most efficient way to connect components while reducing total costs. Its practical importance makes MST algorithms like Kruskal's and Prim's essential tools in both academic and industrial settings.

For anyone looking to deepen their understanding of algorithms or improve their problem-solving skills, implementing MST algorithms is a great start. Platforms like HackerRank, Codeforces, and LeetCode offer numerous MST-related challenges that provide a hands-on way to apply these concepts and develop programming proficiency.

Challenge yourself to solve MST problems and explore how optimization can make complex systems more efficient!