Implement Kruskal’s algorithm and run it on a weighted graph of your own creatio
ID: 3689333 • Letter: I
Question
Implement Kruskal’s algorithm and run it on a weighted graph of your own creation. The algorithm is used to find the minimum spanning tree in a graph. This is a greedy algorithm that examines each edge of the graph and only keeps the connections that are the smallest while still keeping a connection to that node. For more information look here: http://en.wikipedia.org/wiki/Kruskal%27s_algorithm Demonstrate the algorithm works by printing out every edge with weights in your graph, and then printing out the minimum spanning tree.
Explanation / Answer
Kruskal’s Algorithm
Kruskal’s Algorithm is a algorithm to obtaining minimum spanning tree. In this algorithm always the minimum cost edge has to be selected. But it is not necessary that selected optimum edge is adjacent.
Algorithm :
1. start
2. Using the given graph create the edge list, with their corresponding weights.
3. sort the edge list according to the their weights in ther ascending order.
4. using all the nodes, draw a skeleton for spanning tree.
5. Pick up the edge , whose edge weight is minimum (top of the edge in list , list is arranged by ascending order)
6. remove taht6 edge form the list.
7. Connect the vertices to the given edge to the skeleton. If the skeleton forms a cycle by connecting the vertices , remove that edge
8. Repeat the 5,6,7 steps , until n-1 edges are added.
I implement the Kruskal’s Algorithm program in c
Program :
#include<stdio.h>
#define max 50
typedef struct edge
{
int u,v,w;
}edge;
typedef struct edgelist
{
edge data[max];
int n;
}edgelist;
edgelist elist;
int gph[max][max],n;
edgelist span;
void kruskal();
int find(int b[],int vno);
void join(int b[],int c1,int c2);
void sort();
void display();
void main()
{
int i,j,totalcost;
printf(" Enter number of vertices :");
scanf("%d",&n);
printf(" Enter the adjacency matrix : ");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&gph[i][j]);
kruskal();
display();
}
void kruskal()
{
int b[max],i,j,cnum1,cnum2;
elist.n=0;
for(i=1;i<n;i++)
for(j=0;j<i;j++)
{
if(gph[i][j]!=0)
{
elist.data[elist.n].u=i;
elist.data[elist.n].v=j;
elist.data[elist.n].w=gph[i][j];
elist.n++;
}
}
sort();
for(i=0;i<n;i++)
b[i]=i;
span.n=0;
for(i=0;i<elist.n;i++)
{
cnum1=find(b,elist.data[i].u);
cnum2=find(b,elist.data[i].v);
if(cnum1!=cnum2)
{
span.data[span.n]=elist.data[i];
span.n=span.n+1;
join(b,cnum1,cnum2);
}
}
}
int find(int b[],int vno)
{
return(b[vno]);
}
void join(int b[],int c1,int c2)
{
int i;
for(i=0;i<n;i++)
if(b[i]==c2)
b[i]=c1;
}
void sort()
{
int i,j;
edge tmp;
for(i=1;i<elist.n;i++)
for(j=0;j<elist.n-1;j++)
if(elist.data[j].w>elist.data[j+1].w)
{
tmp=elist.data[j];
elist.data[j]=elist.data[j+1];
elist.data[j+1]=tmp;
}
}
void display()
{
int i,cost=0;
for(i=0;i<span.n;i++)
{
printf(" %d %d %d",span.data[i].u,span.data[i].v,span.data[i].w);
cost=cost+span.data[i].w;
}
printf(" Cost of the spanning tree = %d",cost);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.