Open In App

Kruskal's Algorithm (Simple Implementation for Adjacency Matrix)

Last Updated : 20 Mar, 2023
Suggest changes
Share
Like Article
Like
Report

Below are the steps for finding MST using Kruskal's algorithm 

  1. Sort all the edges in non-decreasing order of their weight. 
  2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it. 
  3. Repeat step#2 until there are (V-1) edges in the spanning tree.

We have discussed one implementation of Kruskal's algorithm in previous post. In this post, a simpler implementation for adjacency matrix is discussed. 

Implementation:

C++ 
// Simple C++ implementation for Kruskal's // algorithm #include <bits/stdc++.h> using namespace std; #define V 5 int parent[V]; // Find set of vertex i int find(int i) {  while (parent[i] != i)  i = parent[i];  return i; } // Does union of i and j. It returns // false if i and j are already in same // set. void union1(int i, int j) {  int a = find(i);  int b = find(j);  parent[a] = b; } // Finds MST using Kruskal's algorithm void kruskalMST(int cost[][V]) {  int mincost = 0; // Cost of min MST.  // Initialize sets of disjoint sets.  for (int i = 0; i < V; i++)  parent[i] = i;  // Include minimum weight edges one by one  int edge_count = 0;  while (edge_count < V - 1) {  int min = INT_MAX, a = -1, b = -1;  for (int i = 0; i < V; i++) {  for (int j = 0; j < V; j++) {  if (find(i) != find(j) && cost[i][j] < min) {  min = cost[i][j];  a = i;  b = j;  }  }  }  union1(a, b);  printf("Edge %d:(%d, %d) cost:%d \n",  edge_count++, a, b, min);  mincost += min;  }  printf("\n Minimum cost= %d \n", mincost); } // driver program to test above function int main() {  /* Let us create the following graph  2 3  (0)--(1)--(2)  | / \ |  6| 8/ \5 |7  | / \ |  (3)-------(4)  9 */  int cost[][V] = {  { INT_MAX, 2, INT_MAX, 6, INT_MAX },  { 2, INT_MAX, 3, 8, 5 },  { INT_MAX, 3, INT_MAX, INT_MAX, 7 },  { 6, 8, INT_MAX, INT_MAX, 9 },  { INT_MAX, 5, 7, 9, INT_MAX },  };  // Print the solution  kruskalMST(cost);  return 0; }
Java 
// Simple Java implementation for Kruskal's // algorithm import java.util.*; class GFG  { static int V = 5; static int[] parent = new int[V]; static int INF = Integer.MAX_VALUE; // Find set of vertex i static int find(int i) {  while (parent[i] != i)  i = parent[i];  return i; } // Does union of i and j. It returns // false if i and j are already in same // set. static void union1(int i, int j) {  int a = find(i);  int b = find(j);  parent[a] = b; } // Finds MST using Kruskal's algorithm static void kruskalMST(int cost[][]) {  int mincost = 0; // Cost of min MST.  // Initialize sets of disjoint sets.  for (int i = 0; i < V; i++)  parent[i] = i;  // Include minimum weight edges one by one  int edge_count = 0;  while (edge_count < V - 1)  {  int min = INF, a = -1, b = -1;  for (int i = 0; i < V; i++)  {  for (int j = 0; j < V; j++)   {  if (find(i) != find(j) && cost[i][j] < min)   {  min = cost[i][j];  a = i;  b = j;  }  }  }  union1(a, b);  System.out.printf("Edge %d:(%d, %d) cost:%d \n",  edge_count++, a, b, min);  mincost += min;  }  System.out.printf("\n Minimum cost= %d \n", mincost); } // Driver code public static void main(String[] args)  { /* Let us create the following graph  2 3  (0)--(1)--(2)  | / \ |  6| 8/ \5 |7  | / \ |  (3)-------(4)  9 */  int cost[][] = {  { INF, 2, INF, 6, INF },  { 2, INF, 3, 8, 5 },  { INF, 3, INF, INF, 7 },  { 6, 8, INF, INF, 9 },  { INF, 5, 7, 9, INF },  };  // Print the solution  kruskalMST(cost);  } } // This code contributed by Rajput-Ji
Python3 
# Python implementation for Kruskal's # algorithm # Find set of vertex i def find(i): while parent[i] != i: i = parent[i] return i # Does union of i and j. It returns # false if i and j are already in same  # set.  def union(i, j): a = find(i) b = find(j) parent[a] = b # Finds MST using Kruskal's algorithm  def kruskalMST(cost): mincost = 0 # Cost of min MST # Initialize sets of disjoint sets for i in range(V): parent[i] = i # Include minimum weight edges one by one  edge_count = 0 while edge_count < V - 1: min = INF a = -1 b = -1 for i in range(V): for j in range(V): if find(i) != find(j) and cost[i][j] < min: min = cost[i][j] a = i b = j union(a, b) print('Edge {}:({}, {}) cost:{}'.format(edge_count, a, b, min)) edge_count += 1 mincost += min print("Minimum cost= {}".format(mincost)) # Driver code  # Let us create the following graph  # 2 3  # (0)--(1)--(2)  # | / \ |  # 6| 8/ \5 |7  # | / \ |  # (3)-------(4)  # 9 V = 5 parent = [i for i in range(V)] INF = float('inf') cost = [[INF, 2, INF, 6, INF], [2, INF, 3, 8, 5], [INF, 3, INF, INF, 7], [6, 8, INF, INF, 9], [INF, 5, 7, 9, INF]] # Print the solution  kruskalMST(cost) # This code is contributed by ng24_7
C# 
// Simple C# implementation for Kruskal's // algorithm using System;  class GFG  { static int V = 5; static int[] parent = new int[V]; static int INF = int.MaxValue; // Find set of vertex i static int find(int i) {  while (parent[i] != i)  i = parent[i];  return i; } // Does union of i and j. It returns // false if i and j are already in same // set. static void union1(int i, int j) {  int a = find(i);  int b = find(j);  parent[a] = b; } // Finds MST using Kruskal's algorithm static void kruskalMST(int [,]cost) {  int mincost = 0; // Cost of min MST.  // Initialize sets of disjoint sets.  for (int i = 0; i < V; i++)  parent[i] = i;  // Include minimum weight edges one by one  int edge_count = 0;  while (edge_count < V - 1)  {  int min = INF, a = -1, b = -1;  for (int i = 0; i < V; i++)  {  for (int j = 0; j < V; j++)   {  if (find(i) != find(j) && cost[i, j] < min)   {  min = cost[i, j];  a = i;  b = j;  }  }  }  union1(a, b);  Console.Write("Edge {0}:({1}, {2}) cost:{3} \n",  edge_count++, a, b, min);  mincost += min;  }  Console.Write("\n Minimum cost= {0} \n", mincost); } // Driver code public static void Main(String[] args)  { /* Let us create the following graph  2 3  (0)--(1)--(2)  | / \ |  6| 8/ \5 |7  | / \ |  (3)-------(4)  9 */  int [,]cost = {  { INF, 2, INF, 6, INF },  { 2, INF, 3, 8, 5 },  { INF, 3, INF, INF, 7 },  { 6, 8, INF, INF, 9 },  { INF, 5, 7, 9, INF },  };  // Print the solution  kruskalMST(cost); } } /* This code contributed by PrinciRaj1992 */
JavaScript 
<script> // Simple Javascript implementation for Kruskal's // algorithm var V = 5; var parent = Array(V).fill(0); var INF = 1000000000; // Find set of vertex i function find(i) {  while (parent[i] != i)  i = parent[i];  return i; } // Does union of i and j. It returns // false if i and j are already in same // set. function union1(i, j) {  var a = find(i);  var b = find(j);  parent[a] = b; } // Finds MST using Kruskal's algorithm function kruskalMST(cost) {  var mincost = 0; // Cost of min MST.  // Initialize sets of disjoint sets.  for (var i = 0; i < V; i++)  parent[i] = i;  // Include minimum weight edges one by one  var edge_count = 0;  while (edge_count < V - 1)  {  var min = INF, a = -1, b = -1;  for (var i = 0; i < V; i++)  {  for (var j = 0; j < V; j++)   {  if (find(i) != find(j) && cost[i][j] < min)   {  min = cost[i][j];  a = i;  b = j;  }  }  }  union1(a, b);  document.write(`Edge ${edge_count++}:(${a},   ${b}) cost:${min} <br>`);  mincost += min;  }  document.write(`<br> Minimum cost= ${mincost} <br>`); } // Driver code /* Let us create the following graph  2 3  (0)--(1)--(2)  | / \ |  6| 8/ \5 |7  | / \ |  (3)-------(4)  9 */ var cost = [  [INF, 2, INF, 6, INF],  [2, INF, 3, 8, 5],  [INF, 3, INF, INF, 7],  [6, 8, INF, INF, 9],  [INF, 5, 7, 9, INF]]; // Print the solution kruskalMST(cost); </script>

Output
Edge 0:(0, 1) cost:2 Edge 1:(1, 2) cost:3 Edge 2:(1, 4) cost:5 Edge 3:(0, 3) cost:6 Minimum cost= 16

Time Complexity:
The time complexity of Kruskal's algorithm using the Union-Find algorithm for finding the cycle and sorting the edges is O(E log E + E log V), where E is the number of edges and V is the number of vertices in the graph. 

Space Complexity:
The space complexity of the program is O(V), where V is the number of vertices in the graph.

Note that the above solution is not efficient. The idea is to provide a simple implementation for adjacency matrix representations. Please see below for efficient implementations. 

Kruskal’s Minimum Spanning Tree Algorithm | Greedy Algo-2 
Kruskal’s Minimum Spanning Tree using STL in C++


Next Article
Introduction and implementation of Karger's algorithm for Minimum Cut

A
AnkurKarmakar

Similar Reads

Article Tags :
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy  Cookies are not collected in the GeeksforGeeks mobile applications.
Lightbox