Kruskal’s Algorithm

Kruskal’s algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component).

Algorithm

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

Implementation

#include<stdio.h>
#include<conio.h>
void sort();
bool checkCycle(int,int);
typedef struct edge{
	int src,des;
	int weight;
	};
edge e[100];
int d[100],numberOfEdges;

void main(){
	int n;
	printf("Enter number of nodes\n");
	scanf("%d",&n);
	
	for(int i=0;i< n;i++)
		d[i]=-1;

	printf("Enter number of edges\n");
	scanf("%d",&numberOfEdges);
	for(int i=0;i< numberOfEdges;++i){
		printf("Enter an edge(src des weigth): \n");
		scanf("%d %d %d", &e[i].src , &e[i].des , &e[i].weight);
	}
	sort();
	
	printf("\nEdges :\n");
	int cost=0;
	for(int i=0 ; i
for(int i=0 ; i<n ; i++){
               if( checkCycle (e[i].src , e[i].des ) )
               {
                      cost+=e[i].weight;
                      printf("%d %d = %d\n", e[i].src , e[i].des , e[i].weight); 
               }
        }
        printf("min cost = %d",cost);
        getch();
}

void sort(){
        edge temp;
        for(int i=0;i< numberOfEdges-1;i++)
              for(int j=i+1;j< numberOfEdges;j++)
                    if(e[j].weight < e[i].weight)
                    {
                            temp=e[j];
                            e[j]=e[i];
                            e[i]=temp;
                    }
}

bool checkCycle(int src,int des){ 
        while(d[des]!=-1)
               des = d[des];
        while(d[src]!=-1)
               src = d[src];

       if(src!=des){
               d[des]=src;
               return true;
       }
       return false;
}

Complexity

Where E is the number of edges in the graph and V is the number of vertices, Kruskal’s algorithm can be shown to run in O(E log E) time, or equivalently, O(E log V) time, all with simple data structures. These running times are equivalent because:

  • E is at most V2 and log(V2 )=2log(V)\; is O(log V).
  • Each isolated vertex is a separate component of the minimum spanning forest. If we ignore isolated vertices we obtain VE+1, so log V is O(log E).

We can achieve this bound as follows: first sort the edges by weight using a comparison sort in O(E log E) time; this allows the step “remove an edge with minimum weight from S” to operate in constant time. Next, we use a disjoint-set data structure (Union&Find) to keep track of which vertices are in which components. We need to perform O(V) operations, as in each iteration we connects a vertex to the spanning tree, two ‘find’ operations and possibly one union for each edge. Even a simple disjoint-set data structure such as disjoint-set forests with union by rank can perform O(V) operations in O(V log V) time. Thus the total time is O(E log E) = O(E log V).