Algorithms for Coding Interviews in C++/

...

/

Solution: Find the Minimum Spanning Tree - Kruskal’s Solution

Solution: Find the Minimum Spanning Tree - Kruskal’s Solution

In this review, we give a detailed analysis on finding the minimum spanning tree of the given graph using Kruskal's solution.

We'll cover the following...

Solution: Kruskal’s Algorithm

Kruskal’s algorithm is a minimum-spanning-tree algorithm that finds an edge of the least possible weight.

It is a greedy algorithm, as it finds a minimum spanning tree for a connected weighted graph—adding increasing cost arcs at each step.

C++
#include "Graph.h"
#include "DisjointSets.h"
typedef pair <int, int> myPair;
int Graph::kruskalMST() {
  int weightOfMST = 0;
  // lets first sort all the edges.
  sort(edgesArray.begin(), edgesArray.end());
  DisjointSets mySetDataStructure(this -> vertices);
  vector <pair <int, myPair>> ::iterator iterator;
  for (iterator = edgesArray.begin(); iterator != edgesArray.end(); iterator++) {
    int u = iterator -> second.first;
    int v = iterator -> second.second;
    int set_u = mySetDataStructure.find(u);
    int set_v = mySetDataStructure.find(v);
    if (set_u != set_v) {
      cout << u << " -- " << v << endl;
      weightOfMST += iterator -> first;
      mySetDataStructure.merge(set_u, set_v);
    }
  }
  return weightOfMST;
}
int main() {
  int V = 4, E = 5;
  Graph g(V, E);
  g.addEdge(0, 1, 10);
  g.addEdge(0, 2, 6);
  g.addEdge(0, 3, 5);
  g.addEdge(1, 3, 15);
  g.addEdge(2, 3, 4);
  
  cout << "Minimum Spanning Tree of Graph 1" << endl;
  g.kruskalMST();
  cout << endl <<endl;
  //////////////////
  
  V = 6;
  E = 15;
  Graph g2(V, E);
  g2.addEdge(0, 1, 4);
  g2.addEdge(0, 2, 4);
  g2.addEdge(1, 2, 2);
  g2.addEdge(1, 0, 4);
  g2.addEdge(2, 0, 4);
  g2.addEdge(2, 1, 2);
  g2.addEdge(2, 3, 3);
  g2.addEdge(2, 5, 2);
  g2.addEdge(2, 4, 4);
  g2.addEdge(3, 2, 3);
  g2.addEdge(3, 4, 3);
  g2.addEdge(4, 2, 4);
  g2.addEdge(4, 3, 3);
  g2.addEdge(5, 2, 2);
  g2.addEdge(5, 4, 3);
  
  cout << "Minimum Spanning Tree of Graph 2" << endl;
  g2.kruskalMST();
  return 0;
}

Pseudocode

KruskalMST(G):
A = ∅
for each v ∈ G.V:
    MAKE-SET(v)
for each (u, v) in G.E ordered by weight(u, v), increasing:
    if FIND-SET(u) ≠ FIND-SET(v):
       A = A ∪ {(u, v)}
       UNION(u, v)
return A

Animation

The animation below gives a demo of how Kruskal’s algorithm is applied to a graph to find its minimum spanning tree.

Reference

Time Complexity

Sorting of edges takes O(ELogE)O(ELogE) ...