Kruskal’s Algorithm
Algorithm
[This algorithm takes a graph G as an input and w is the weight. Here V[G] are the set of vertices of a graph. (u,v) is an edge between any two vertices u and v. Finally it returns a set A having edges for Minimum spanning tree of G]
Input No. of Vertex , Edges weights between vertices
Output Minimum spanning tree of graph
Complexity O(E lg V)
MST-KRUSKAL(G, w)
1. A ← Ø
2. for each vertex v εV[G]
3. do MAKE-SET(v)
4. sort the edges of E into nondecreasing order by weight w
5. for each edge (u, v) ε E, taken in nondecreasing order by weight
6. do if FIND-SET(u) ≠FIND-SET(v)
7. then A ← A U {(u, v)}
8. UNION(u, v)
9. return A
MAKE-SET(x)
[Here p[x] denote parent of x and initially rank is initialised to 0]
1. p[x] ← x
2. rank[x] ← 0
UNION(x, y)
1. LINK(FIND-SET(x), FIND-SET(y))
LINK(x, y)
1. if rank[x] > rank[y]
2. then p[y] ← x
3. else p[x] ← y
4. if rank[x] = rank[y]
5. then rank[y] ← rank[y] + 1
FIND-SET(x)
1. if x ≠p[x]
2. then p[x] ← FIND-SET(p[x])
3. return p[x]
Algorithm Description
1. MST-KRUSKAL(G, w) step 1-3 initialize the set A to the empty set and create |V| trees, one containing each vertex. The edges in E are sorted into non-decreasing order by weight in line 4. 2. The for loop in lines 5-8 checks, for each edge (u, v), whether the endpoints u and v belong to the same tree. If they do, then the edge (u, v) cannot be added to the forest without creating a cycle, and the edge is discarded. Otherwise, the two vertices belong to different trees. In this case, the edge (u, v) is added to A in line 7, and the vertices in the two trees are merged in line 8. 3. Each call of FIND-SET(x) returns p[x] in line 3. 4. If x is the root, then line 2 is not executed and p[x] = x is returned. 5. Line 2 updates node x to point directly to the root, and this pointer is returned in line 3.
C Code
//WAP to implement Kruskal algorithm for MST
#include<stdio.h>
#include<conio.h>
void makeset();
void graph(int);
void kruskal();
struct node *findset(struct node *);
void union1(struct node *,struct node *);
int j=0;
struct node //Declare the structure of a node
{
int data,rank;
struct node *next,*parent;
};
struct edge //Declare the structure of a edge
{
int len;
struct node *src,*destination;
};
struct node *head[10];
struct edge *e[40];
int main()
{
int n,i;
printf("\nEnter no.of vertices in the graph : ");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
makeset(i); //initialise each vertex
}
graph(n);
kruskal();
getch();
}
void makeset(int a)
{
struct node *x;
x=(struct node*)malloc(sizeof(struct node));
x->data=a;
x->parent=x;
x->rank=0;
x->next=NULL;
head[a]=x;
}
void graph(int n) //here input neighbours of each vertex & the weight of edges
{
int i,k,l,len;
int dest;
for(i=1;i<=n;i++)
{
printf("\nfor vertex %d Enter no. of edges ",i);
scanf("%d",&l);
for(k=1;k<=l;k++)
{
printf("Enter destination vertex for %dth edge for vertex %d ",k,i);
scanf("%d",&dest);
j++;
e[j]=(struct edge*)malloc(sizeof(struct edge));
e[j]->src=head[i];
e[j]->destination=head[dest];
printf("Enter length of edge : ");
scanf("%d",&len);
e[j]->len=len;
}
}
}
void kruskal() //Apply actual concept of kruskal
{
int i,k,l,p;
struct edge *temp;
i=1;
while(i<j) //sort the edges with increasing order of their weights
{ //using insertion sort
p=i;
k=i+1;
while(k<=j)
{
if(e[p]->len>e[k]->len)
{
p=k;
}
k++;
}
if(p!=i)
{
temp=e[p];
e[p]=e[i];
e[i]=temp;
}
i++;
}
printf("\nMST includes the following edges that are :\n");
for(i=1;i<=j;i++)
{
if(findset(e[i]->src)!=findset(e[i]->destination)) //if representative
{ //of src & dest. are different
union1((findset(e[i]->src)),(findset(e[i]->destination))); //then make connection
printf("\n%d->%d",e[i]->src->data,e[i]->destination->data); //b/w them
}
}
}
struct node *findset(struct node *a) //return the represenative of node a
{
if(a!=a->parent)
{
a->parent=findset(a->parent);
}
return a->parent;
}
void union1(struct node *x,struct node *y) //join the two vertex if desired
{
if(x->rank>y->rank)
y->parent=x;
else
x->parent=y;
if(x->rank==y->rank)
y->rank=y->rank+1;
}
Java Code
import java.io.*;
class kruskal
{static int m[][]= new int[10][10];
static int cost[][]= new int[10][10];
static int a[][]= new int[10][10];
static int b[]= new int[10];
static int i,j,n=0,k=0;
static int sum=0;
static int count=0;
static void enter(int n) throws IOException
{ BufferedReader br= new BufferedReader (new InputStreamReader(System.in));
int i,j,k;
for(i=0;i<n;i++)
for(j=i;j<n;j++)
{
if(i==j)
continue;
System.out.println("\nEnter the value of distance from node"+ i+" to node"+j);
a[i][j]=Integer.parseInt(br.readLine());
if(a[i][j]==0)
a[i][j]=1000;
}
a[0][0]=1000;
for(i=0;i<n;i++)
for(j=0;j<i;j++)
{
a[i][j]=a[j][i];
a[i][i]=1000;
}
}
static void set() throws IOException
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
cost[i][j]=11111;
m[i][j]=0;
}
}
enter(n);
}
static boolean sssp(int sour,int dest) throws IOException
{ BufferedReader br= new BufferedReader (new InputStreamReader(System.in));
int i,j;
int distance[]= new int[20];
int prev[]=new int[20];
int prevmatrix[][]= new int[20][20];
int source=sour;
for( i=0;i<n;i++)
{
prev[i]=source;
if(i==source)
distance[i]=11111;
else
{
distance[i]=cost[source][i];
}
}
int t[]=new int[20];int temp[]=new int[20];
int z=0, min=source;
int eachnode=0;
while(eachnode<n)
{ min=source;
for( i=0;i<n;i++)
{
if(distance[min]>distance[i])
min=i;
}
t[z]=min;z++;
temp[min]=distance[min];
distance[min]=11111;
j=0;
for(j=0;j<n;j++)
{ int min1=1;
for(int k=0;k<z;k++)
{
if(j==t[k])
min1=0;
}
if((j!=min&&j!=source&&min1==1))
{
if((distance[j]>temp[min]+cost[min][j])&&cost[min][j]!=11111)
{
distance[j]=temp[min]+cost[min][j];
prev[j]=min;
}
}
}
eachnode++;
}
for(j=0;j<n;j++)
{
if(temp[j]==11111)
temp[j]=0;
prevmatrix[source][j]=prev[j]+1;
}
if(temp[dest]==0)
return(false);
else
return(true);
}
static void min() throws IOException
{
BufferedReader br= new BufferedReader (new InputStreamReader(System.in));
int i,j,minimum=0,mini,t=0,x=0;
sum=0;
mini=1000;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(a[i][j]<mini && m[i][j]==0)
{
mini=a[i][j];
t=i;x=j;
minimum=mini;
}
}
}
m[t][x]=1;
m[x][t]=1;
if(!sssp(t,x))
{
cost[t][x]=minimum;
cost[x][t]=minimum;
count++;
System.out.println((t+1)+","+(x+1));
}
}
public static void main(String args[]) throws IOException
{ int totalsum=0;
BufferedReader br= new BufferedReader (new InputStreamReader(System.in));
System.out.println("\nif the nodes are disconnected then enter 0");
System.out.println("\nEnter the value of number of nodes");
n=Integer.parseInt(br.readLine());
set();
System.out.println(" order is ");
while(count<n-1)
{
min();
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(cost[i][j]!=11111)
totalsum=totalsum+cost[i][j];
}
} System.out.println("Total Cost is "+(totalsum/2));
}
}
