Kruskal's Minimum Spanning Tree Algorithm

Kruskal’s algorithm is a graph based algorithm which is used to build Minimum Spanning Tree (MST) for a given weighted, undirected graph. It creates MST by greedily adding the cheapest available edge to the tree, as long as it does not create a cycle. The algorithm starts by sorting all the edges in the graph in ascending order of their weights. Then, it iterates through the sorted edges and adds each edge to the MST if it does not create a cycle. The algorithm continues until all the vertices are connected, forming the MST.

What is a Minimum Spanning Tree?

A Minimum Spanning Tree (MST) is a subset of the edges of a connected, weighted graph that connects all the vertices together with the minimum possible total edge weight. In other words, it is the cheapest or minimum cost subgraph in a given graph that connects all the nodes in the graph.

For example, for the undirected weighted graph shown below:

Below is how the minimum spanning tree looks like:

Refer to this article to learn more about Minimum Spanning Trees.

Detailed Steps of Kruskal’s MST Algorithm

Below are the steps involved in Kruskal’s algorithm to find Minimum Spanning Tree (MST) of an undirected and weighted graph:

Preliminary Step: Representation of Graph

Represent the graph as a list of edges, where each edge is a tuple (u, v, w) representing a connection between vertices u and v with weight w.

Step 1: Edge Sorting

Sort all edges in the graph in ascending order based on their weights.

Step 2: Initialization of Data Structure For Detecting Cycles

Create a disjoint set data structure to keep track of connected components.
This data structure is used to check if addition of an edge to the MST will cause any cycles. In other words, this data structure is used to find if the two nodes involved with the current edge are already part of the same set/component.
We use union-find algorithm for merging two nodes into a single component/set while adding an edge to the MST
Initially, each vertex is in its own component.

Step 3: Edge Selection and Component Merging

Iterate through the sorted edges:
- For each edge (u, v, w), determine if vertices u and v belong to different components.
- If they are in different components:
  - Add this edge to the minimum spanning tree.
  - Merge the components containing u and v in the disjoint set data structure.
- If they are in the same component, discard this edge to avoid creating a cycle.

Step 4: Termination

Continue Step 3 until either:
- All vertices are in the same component (indicating a fully connected MST), or
- All edges have been processed.

The final result is the minimum spanning tree, which is a subgraph of the original graph that connects all vertices with the minimum total weight of the edges.

Implementation of Kruskal’s Algorithm


# Function to find the root of a node in the disjoint set
def find_root(parent, node):
  # If the node is not the root, recursively find the root
  if parent[node] != node:
    parent[node] = find_root(parent, parent[node])
  return parent[node]

# Function to union two nodes in the disjoint set
def union_components(parent, node1, node2):
  # Find the roots of the two nodes
  root1 = find_root(parent, node1)
  root2 = find_root(parent, node2)
  
  # Merge/Union both components
  # By setting the parent of one root to the other root
  parent[root1] = root2

# Function to implement Kruskal's MST algorithm
def kruskals_mst(edges, nodes):
  # Initialize the parent info for each node used for disjoint set
  parent = {node:node for node in nodes}
  
  # Sort the edges by weight in ascending order
  edges.sort(key=lambda x: x[2])
  
  # Initialize an array to store all edges in the MST
  mst = []
  total_weight = 0
  
  # Iterate through the sorted edges
  for node1, node2, weight in edges:
    # If the two nodes are not in the same set/component, add the edge to the MST
    if find_root(parent, node1) != find_root(parent, node2):
      mst.append((node1, node2, weight))
      total_weight += weight
      union_components(parent, node1, node2)
  
  return mst, total_weight

if __name__ == "__main__":
  # Example graph represented as edges: (node1, node2, weight)
  edges = [("A", "B", 8), ("A", "D", 2), ("A", "E", 4), ("B", "C", 7), ("B", "F", 4), ("C", "D", 9), ("C", "F", 6), ("D", "E", 5), ("E", "F", 3)]
  nodes = ["A","B","C","D","E","F"]

  mst, total_weight = kruskals_mst(edges, nodes)

  print("Minimum Spanning Tree edges:")
  for edge in mst:
    print(f"({edge[0]} - {edge[1]}) with weight {edge[2]}")
  print(f"Total weight of MST: {total_weight}")


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

using namespace std;

// Function to find the root of a node in the disjoint set
int find_root(vector<int>& parent, int node) {
  // If the node is not the root, recursively find the root
  if (parent[node] != node) {
    parent[node] = find_root(parent, parent[node]);
  }
  return parent[node];
}

// Function to union two nodes in the disjoint set
void union_components(vector<int>& parent, int node1, int node2) {
  // Find the roots of the two nodes
  int root1 = find_root(parent, node1);
  int root2 = find_root(parent, node2);

  // Merge/Union both components
  // By setting the parent of one root to the other root
  parent[root1] = root2;
}

// Function to implement Kruskal's MST algorithm
pair<vector<tuple<int, int, int>>, int> kruskals_mst(vector<tuple<int, int, int>>& edges, int nodes) {
  // Initialize the parent info for each node used for disjoint set
  vector<int> parent(nodes);
  for (int i = 0; i < nodes; i++) {
    parent[i] = i;
  }

  // Sort the edges by weight in ascending order
  sort(edges.begin(), edges.end(), [](const tuple<int, int, int>& a, const tuple<int, int, int>& b) {
    return get<2>(a) < get<2>(b);
  });

  // Initialize an array to store all edges in the MST
  vector<tuple<int, int, int>> mst;
  int total_weight = 0;

  // Iterate through the sorted edges
  for (const auto& edge : edges) {
    int node1, node2, weight;
    tie(node1, node2, weight) = edge;

    // If the two nodes are not in the same set/component, add the edge to the MST
    if (find_root(parent, node1) != find_root(parent, node2)) {
      mst.emplace_back(node1, node2, weight);
      total_weight += weight;
      union_components(parent, node1, node2);
    }
  }

  return {mst, total_weight};
}

int main() {
  // Example graph represented as edges: (node1, node2, weight)
  vector<tuple<int, int, int>> edges = {{0, 1, 8}, {0, 3, 2}, {0, 4, 4}, {1, 2, 7}, {1, 5, 4}, {2, 3, 9}, {2, 5, 6}, {3, 4, 5}, {4, 5, 3}};
  int nodes = 6;

  auto [mst, total_weight] = kruskals_mst(edges, nodes);

  cout << "Minimum Spanning Tree edges:" << endl;
  for (const auto& edge : mst) {
    int node1, node2, weight;
    tie(node1, node2, weight) = edge;
    cout << "(" << node1 << " - " << node2 << ") with weight " << weight << endl;
  }
  cout << "Total weight of MST: " << total_weight << endl;

  return 0;
}


// Function to find the root of a node in the disjoint set
function findRoot(parent, node) {
  // If the node is not the root, recursively find the root
  if (parent[node] !== node) {
    parent[node] = findRoot(parent, parent[node]);
  }
  return parent[node];
}

// Function to union two nodes in the disjoint set
function unionComponents(parent, node1, node2) {
  // Find the roots of the two nodes
  const root1 = findRoot(parent, node1);
  const root2 = findRoot(parent, node2);

  // Merge/Union both components
  // By setting the parent of one root to the other root
  parent[root1] = root2;
}

// Function to implement Kruskal's MST algorithm
function kruskalsMinimumSpanningTree(edges, nodes) {
  // Initialize the parent info for each node used for disjoint set
  const parent = {};
  nodes.forEach((node) => {
    parent[node] = node;
  });

  // Sort the edges by weight in ascending order
  edges.sort((a, b) => a[2] - b[2]);

  // Initialize an array to store all edges in the MST
  const mst = [];
  let totalWeight = 0;

  // Iterate through the sorted edges
  for (const [node1, node2, weight] of edges) {
    // If the two nodes are not in the same set/component, add the edge to the MST
    if (findRoot(parent, node1) !== findRoot(parent, node2)) {
      mst.push([node1, node2, weight]);
      totalWeight += weight;
      unionComponents(parent, node1, node2);
    }
  }

  return [mst, totalWeight];
}

// Example usage
const edges = [["A", "B", 8], ["A", "D", 2], ["A", "E", 4], ["B", "C", 7], ["B", "F", 4], ["C", "D", 9], ["C", "F", 6], ["D", "E", 5], ["E", "F", 3]];
const nodes = ["A", "B", "C", "D", "E", "F"];

const [mst, totalWeight] = kruskalsMinimumSpanningTree(edges, nodes);

console.log("Minimum Spanning Tree edges:");
for (const [node1, node2, weight] of mst) {
  console.log(`(${node1} - ${node2}) with weight ${weight}`);
}
console.log(`Total weight of MST: ${totalWeight}`);

Time & Space Complexity

Time Complexity

The time complexity of Kruskal’s algorithm for finding Minimum Spanning Tree in a graph is O(E log E), where E is the number of edges present in the graph.

The reason for this time complexity is as follows:

Sorting the edges: The first step of Kruskal’s algorithm is to sort the edges in ascending order of their weights. This step takes O(E log E) time.
Checking for cycles: As the algorithm progresses, it checks whether adding an edge to the MST would create a cycle. This is done using a data structure called a disjoint-set (or union-find) data structure, which allows for efficient checking of whether two vertices are in the same connected component. Efficient implementations of disjoint-set data structure brings the overall time complexity of this step to O(E).
Adding edges to the MST: The final step is to add the edges to the MST. This can be done in O(1) time per edge, as it involves appending the edge to the end of MST array.

Combining these steps, the overall time complexity of Kruskal’s algorithm is O(E log E).

Space Complexity

The space complexity of Kruskal’s algorithm is O(V + E), where V is the number of vertices and E is the number of edges in the graph.

The reason for this space complexity is as follows:

Storing the graph: The algorithm needs to sort and store all edges in the graph, which requires O(E) space.
Storing the disjoint-set data structure: The algorithm uses a disjoint-set data structure to keep track of the connected components in the graph. This data structure requires O(V) space to store the parent information for each vertex.

Combining these space requirements, the overall space complexity of Kruskal’s algorithm is O(V + E).