Kruskal 's Algorithm (Simple Implementation for Adjacency Matrix) | Simple C ++ implementation for Kruskal 's algorithm ; Find set of vertex i ; Does union of i and j . It returns false if i and j are already in same set . ; Finds MST using Kruskal 's algorithm ; Initialize sets of disjoint sets . ; Include minimum weight edges one by one ; driver program to test above function ; Let us create the following graph 2 3 ( 0 ) -- ( 1 ) -- ( 2 ) | / \ | 6 | 8 / \ 5 | 7 | / \ | ( 3 ) -- -- -- - ( 4 ) 9 ; Print the solution
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define V  5 NEW_LINE int parent [ V ] ; int find ( int i ) { while ( parent [ i ] != i ) i = parent [ i ] ; return i ; } void union1 ( int i , int j ) { int a = find ( i ) ; int b = find ( j ) ; parent [ a ] = b ; } void kruskalMST ( int cost [ ] [ V ] ) { for ( int i = 0 ; i < V ; i ++ ) parent [ i ] = i ; 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 ▁ STRNEWLINE " , edge_count ++ , a , b , min ) ; mincost += min ; } printf ( " Minimum cost = % d " , mincost ) ; } int main ( ) { 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 } , } ; kruskalMST ( cost ) ; return 0 ; }