Krushkal Algorithm:
Step 1: Start
Step 2: Read a weighted Graph G(V, E)
Step 3: Let n be the number of vertices in the graph G
Step 4: Find the lowest cost edge and draw it
Step 5: Choose the next lowest cost edge
Step 6: if a cycle is formed if this lowest cost edge is drawn then
Take the next lowest cost edge
Step 7: else
Draw the edge
Step 8: Go to step 3 until n-1 edges are drawn
Step 9: STOP
===========================================================
Program:
#include<stdio.h>
int find(int i);
void union1(int,int);
int parent[10];
struct sample
{
int u;
int v;
int cost;
};
typedef struct sample krushkals;
int sample(krushkals[],int,int);
main()
{
krushkals d[10];
int n,e,i,mincost;
printf("enter number of vertices\n");
scanf("%d",&n);
printf("enter number of edges\n");
scanf("%d",&e);
for(i=1;i<=e;i++)
{
printf("enter the starting vertex\n");
scanf("%d",&d[i].u);
printf("enter the ending vertex\n");
scanf("%d",&d[i].v);
printf("enter their costs\n");
scanf("%d",&d[i].cost);
}
mincost=sample(d,e,n);
printf("mincost of a spanning tree is %d",mincost);
}
int sample(krushkals d[10],int e,int n)
{
int mincost=0;
int j,l,k,u,v,i;
int t[10][10];
krushkals temp;
for(i=1;i<e;i++)
{
for(j=i+1;j<=e;j++)
{
if(d[i].cost>d[j].cost)
{
temp=d[i];
d[i]=d[j];
d[j]=temp;
}
}
}
for(i=1;i<=n;i++)
parent[i]=-1;
i=1;
l=1;
while(i<=n-1&&l<=e)
{
j=find(d[l].u);
k=find(d[l].v);
if(j!=k)
{
t[i][1]=d[l].u;
t[i][2]=d[l].v;
printf("t[%d][1]=%d\n",i,d[l].u);
printf("t[%d][2]=%d\n",i,d[l].v);
printf("path is %d->%d\n",d[l].u,d[l].v);
mincost=mincost+d[l].cost;
i++;
union1(j,k);
}
l++;
}
if(i!=n)
printf("no spanning tree\n");
else
return mincost;
}
int find(int i)
{
while(parent[i]!=-1)
{
i=parent[i];
}
return i;
}
void union1(int i,int j)
{
parent[i]=j;
}
Step 1: Start
Step 2: Read a weighted Graph G(V, E)
Step 3: Let n be the number of vertices in the graph G
Step 4: Find the lowest cost edge and draw it
Step 5: Choose the next lowest cost edge
Step 6: if a cycle is formed if this lowest cost edge is drawn then
Take the next lowest cost edge
Step 7: else
Draw the edge
Step 8: Go to step 3 until n-1 edges are drawn
Step 9: STOP
===========================================================
Program:
#include<stdio.h>
int find(int i);
void union1(int,int);
int parent[10];
struct sample
{
int u;
int v;
int cost;
};
typedef struct sample krushkals;
int sample(krushkals[],int,int);
main()
{
krushkals d[10];
int n,e,i,mincost;
printf("enter number of vertices\n");
scanf("%d",&n);
printf("enter number of edges\n");
scanf("%d",&e);
for(i=1;i<=e;i++)
{
printf("enter the starting vertex\n");
scanf("%d",&d[i].u);
printf("enter the ending vertex\n");
scanf("%d",&d[i].v);
printf("enter their costs\n");
scanf("%d",&d[i].cost);
}
mincost=sample(d,e,n);
printf("mincost of a spanning tree is %d",mincost);
}
int sample(krushkals d[10],int e,int n)
{
int mincost=0;
int j,l,k,u,v,i;
int t[10][10];
krushkals temp;
for(i=1;i<e;i++)
{
for(j=i+1;j<=e;j++)
{
if(d[i].cost>d[j].cost)
{
temp=d[i];
d[i]=d[j];
d[j]=temp;
}
}
}
for(i=1;i<=n;i++)
parent[i]=-1;
i=1;
l=1;
while(i<=n-1&&l<=e)
{
j=find(d[l].u);
k=find(d[l].v);
if(j!=k)
{
t[i][1]=d[l].u;
t[i][2]=d[l].v;
printf("t[%d][1]=%d\n",i,d[l].u);
printf("t[%d][2]=%d\n",i,d[l].v);
printf("path is %d->%d\n",d[l].u,d[l].v);
mincost=mincost+d[l].cost;
i++;
union1(j,k);
}
l++;
}
if(i!=n)
printf("no spanning tree\n");
else
return mincost;
}
int find(int i)
{
while(parent[i]!=-1)
{
i=parent[i];
}
return i;
}
void union1(int i,int j)
{
parent[i]=j;
}
No comments:
Post a Comment