Write a Program to implement kruskal's algorithm in c?

Answer 1

/* Program for creating a minimum spanning tree from Kruskal's

algorithm */

#include

#define MAX 20

struct edge

{

int u;

int v;

int weight;

struct edge *link;

}*front = NULL;

int father[MAX]; /*Holds father of each node */

struct edge tree[MAX]; /* Will contain the edges of spanning tree */

int n; /*Denotes total number of nodes in the graph */

int wt_tree=0; /*Weight of the spanning tree */

int count=0; /* Denotes number of edges included in the tree */

/* Functions */

void make_tree();

void insert_tree(int i,int j,int wt);

void insert_pque(int i,int j,int wt);

struct edge *del_pque();

main()

{

int i;

create_graph();

make_tree();

printf("Edges to be included in spanning tree are :\n");

for(i=1;i<=count;i++)

{

printf("%d->",tree[i].u);

printf("%d\n",tree[i].v);

}

printf("Weight of this minimum spanning tree is : %d\n", wt_tree);

}/*End of main()*/

create_graph()

{

int i,wt,max_edges,origin,destin;

printf("Enter number of nodes : ");

scanf("%d",&n);

max_edges=n*(n-1)/2;

for(i=1;i<=max_edges;i++)

{

printf("Enter edge %d(0 0 to quit): ",i);

scanf("%d %d",&origin,&destin);

if( (origin==0) && (destin==0) )

break;

printf("Enter weight for this edge : ");

scanf("%d",&wt);

if( origin > n destin > n origin<=0 destin<=0)

{

printf("Invalid edge!\n");

i--;

}

else

insert_pque(origin,destin,wt);

}/*End of for*/

if(i

{

printf("Spanning tree is not possible\n");

exit(1);

}

}/*End of create_graph()*/

void make_tree()

{

struct edge *tmp;

int node1,node2,root_n1,root_n2;

while( count < n-1) /*Loop till n-1 edges included in the tree*/

{

tmp=del_pque();

node1=tmp->u;

node2=tmp->v;

printf("n1=%d ",node1);

printf("n2=%d ",node2);

while( node1 > 0)

{

root_n1=node1;

node1=father[node1];

}

while( node2 >0 )

{

root_n2=node2;

node2=father[node2];

}

printf("rootn1=%d ",root_n1);

printf("rootn2=%d\n",root_n2);

if(root_n1!=root_n2)

{

insert_tree(tmp->u,tmp->v,tmp->weight);

wt_tree=wt_tree+tmp->weight;

father[root_n2]=root_n1;

}

}/*End of while*/

}/*End of make_tree()*/

/*Inserting an edge in the tree */

void insert_tree(int i,int j,int wt)

{

printf("This edge inserted in the spanning tree\n");

count++;

tree[count].u=i;

tree[count].v=j;

tree[count].weight=wt;

}/*End of insert_tree()*/

/*Inserting edges in the priority queue */

void insert_pque(int i,int j,int wt)

{

struct edge *tmp,*q;

tmp = (struct edge *)malloc(sizeof(struct edge));

tmp->u=i;

tmp->v=j;

tmp->weight = wt;

/*Queue is empty or edge to be added has weight less than first edge*/

if( front NULL) /*Edge to be added at the end*/

tmp->link = NULL;

}/*End of else*/

}/*End of insert_pque()*/

/*Deleting an edge from the priority queue*/

struct edge *del_pque()

{

struct edge *tmp;

tmp = front;

printf("Edge processed is %d->%d %d\n",tmp->u,tmp->v,tmp->weight);

front = front->link;

return tmp;

}/*End of del_pque()*/

Answer 2

#include<iostream.h>

class kruskal

{

private:

int n; //no of nodes

int noe; //no edges in the graph

int graph_edge[100][4];

int tree[10][10];

int sets[100][10];

int top[100];

public:

void read_graph();

void initialize_span_t();

void sort_edges();

void algorithm();

int find_node(int );

void print_min_span_t();

};

void kruskal::read_graph()

{

cout<<"*************************************************\n"

<<"This program implements the kruskal algorithm\n"

<<"*************************************************\n";

cout<<"Enter the no. of nodes in the undirected weighted graph ::";

cin>>n;

noe=0;

cout<<"Enter the weights for the following edges ::\n";

for(int i=1;i<=n;i++)

{

for(int j=i+1;j<=n;j++)

{

cout<<" < "<<i<<" , "<<j<<" > ::";

int w;

cin>>w;

if(w!=0)

{

noe++;

graph_edge[noe][1]=i;

graph_edge[noe][2]=j;

graph_edge[noe][3]=w;

}

}

}

// print the graph edges

cout<<"\n\nThe edges in the given graph are::\n";

for(i=1;i<=noe;i++)

cout<<" < "<<graph_edge[i][1]

<<" , "<<graph_edge[i][2]

<<" > ::"<<graph_edge[i][3]<<endl;

}

void kruskal::sort_edges()

{

/**** Sort the edges using bubble sort in increasing order**************/

for(int i=1;i<=noe-1;i++)

{

for(int j=1;j<=noe-i;j++)

{

if(graph_edge[j][3]>graph_edge[j+1][3])

{

int t=graph_edge[j][1];

graph_edge[j][1]=graph_edge[j+1][1];

graph_edge[j+1][1]=t;

t=graph_edge[j][2];

graph_edge[j][2]=graph_edge[j+1][2];

graph_edge[j+1][2]=t;

t=graph_edge[j][3];

graph_edge[j][3]=graph_edge[j+1][3];

graph_edge[j+1][3]=t;

}

}

}

// print the graph edges

cout<<"\n\nAfter sorting the edges in the given graph are::\n";

for(i=1;i<=noe;i++)

cout<<" < "<<graph_edge[i][1]

<<" , "<<graph_edge[i][2]

<<" > ::"<<graph_edge[i][3]<<endl;

}

void kruskal::algorithm()

{

// ->make a set for each node

for(int i=1;i<=n;i++)

{

sets[i][1]=i;

top[i]=1;

}

cout<<"\nThe algorithm starts ::\n\n";

for(i=1;i<=noe;i++)

{

int p1=find_node(graph_edge[i][1]);

int p2=find_node(graph_edge[i][2]);

if(p1!=p2)

{

cout<<"The edge included in the tree is ::"

<<" < "<<graph_edge[i][1]<<" , "

<<graph_edge[i][2]<<" > "<<endl<<endl;

tree[graph_edge[i][1]][graph_edge[i][2]]=graph_edge[i][3];

tree[graph_edge[i][2]][graph_edge[i][1]]=graph_edge[i][3];

// Mix the two sets

for(int j=1;j<=top[p2];j++)

{

top[p1]++;

sets[p1][top[p1]]=sets[p2][j];

}

top[p2]=0;

}

else

{

cout<<"Inclusion of the edge "

<<" < "<<graph_edge[i][1]<<" , "

<<graph_edge[i][2]<<" > "<<"forms a cycle so it is removed\n\n";

}

}

}

int kruskal::find_node(int n)

{

for(int i=1;i<=noe;i++)

{

for(int j=1;j<=top[i];j++)

{

if(n==sets[i][j])

return i;

}

}

return -1;

}

int main()

{

kruskal obj;

obj.read_graph();

obj.sort_edges();

obj.algorithm();

return 0;

}

Answer 3

Hi,

I have an GUI application for this that is written in C++ if it helps.

At the end of the posting there is code you can download as well:

http://andyuk2010.blogspot.com/2010/04/finding-minimal-spanning-trees-using.html

Hope this helps.

I use the Boost libraries to implement the actual Kruskal algorithm

rather than invent it from scratch.

Cheers

Andy

Answer 4

#include < stdio.h>

#include < conio.h>

typedef struct

{

int node1;

int node2;

int wt;

}edge;

void sortedges(edge a[],int n)

{

int i,j;

edge temp;

for(i=0;i< n-1;++i)

for(j=i+1;j< n;++j)

if(a[i].wt>a[j].wt){temp=a[i];a[i]=a[j];a[j]=temp;}

}

int checkcycle(int p[],int i,int j)

{

int v1,v2;

v1 = i;

v2 = j;

while(p[i]>-1)

i = p[i];

while(p[j]>-1)

j = p[j];

if(i!=j)

{

p[j]=i;

printf("%d %d\n",v1,v2);

return 1;

}

return 0;

}

void main()

{

edge e[100];

int parent[100];

int n,i,j,m,k = 1,cost = 0;

clrscr();

printf("KRUSKAL's ALGORITHM\n");

printf("Enter number of nodes\n");

scanf("%d",&n);

for(i=0;i< n;++i)

parent[i]=-1;

i = 0;

printf("Enter number of edges\n");

scanf("%d",&m);

for(i=0;i< m;++i)

{

printf("enter an edge and wt\n");

scanf("%d %d %d", &e[i].node1,&e[i].node2,&e[i].wt);

}

sortedges(e,m);

printf("\n\nEdges of the tree\n");

i = 0;

while(k< n)

{

if(checkcycle(parent,e[i].node1,e[i].node2))

{

k++;

cost=cost+e[i].wt;

i++;

}

}

printf("cost = %d",cost);

getch();

}

Answer 5

#include <stdio.h> #include <conio.h> #include <alloc.h> struct lledge { int v1, v2 ; float cost ; struct lledge *next ; } ; int stree[5] ; int count[5] ; int mincost ; struct lledge * kminstree ( struct lledge *, int ) ; int getrval ( int ) ; void combine ( int, int ) ; void del ( struct lledge * ) ; void main( ) { struct lledge *temp, *root ; int i ; clrscr( ) ; root = ( struct lledge * ) malloc ( sizeof ( struct lledge ) ) ; root -> v1 = 4 ; root -> v2 = 3 ; root -> cost = 1 ; temp = root -> next = ( struct lledge * ) malloc ( sizeof ( struct lledge ) ) ; temp -> v1 = 4 ; temp -> v2 = 2 ; temp -> cost = 2 ; temp -> next = ( struct lledge * ) malloc ( sizeof ( struct lledge ) ) ; temp = temp -> next ; temp -> v1 = 3 ; temp -> v2 = 2 ; temp -> cost = 3 ; temp -> next = ( struct lledge * ) malloc ( sizeof ( struct lledge ) ) ; temp = temp -> next ; temp -> v1 = 4 ; temp -> v2 = 1 ; temp -> cost = 4 ; temp -> next = NULL ; root = kminstree ( root, 5 ) ; for ( i = 1 ; i <= 4 ; i++ ) printf ( "\nstree[%d] -> %d", i, stree[i] ) ; printf ( "\nThe minimum cost of spanning tree is %d", mincost ) ; del ( root ) ; getch( ) ; } struct lledge * kminstree ( struct lledge *root, int n ) { struct lledge *temp = NULL ; struct lledge *p, *q ; int noofedges = 0 ; int i, p1, p2 ; for ( i = 0 ; i < n ; i++ ) stree[i] = i ; for ( i = 0 ; i < n ; i++ ) count[i] = 0 ; while ( ( noofedges < ( n - 1 ) ) && ( root != NULL ) ) { p = root ; root = root -> next ; p1 = getrval ( p -> v1 ) ; p2 = getrval ( p -> v2 ) ; if ( p1 != p2 ) { combine ( p -> v1, p -> v2 ) ; noofedges++ ; mincost += p -> cost ; if ( temp == NULL ) { temp = p ; q = temp ; } else { q -> next = p ; q = q -> next ; } q -> next = NULL ; } } return temp ; } int getrval ( int i ) { int j, k, temp ; k = i ; while ( stree[k] != k ) k = stree[k] ; j = i ; while ( j != k ) { temp = stree[j] ; stree[j] = k ; j = temp ; } return k ; } void combine ( int i, int j ) { if ( count[i] < count[j] ) stree[i] = j ; else { stree[j] = i ; if ( count[i] == count[j] ) count[j]++ ; } } void del ( struct lledge *root ) { struct lledge *temp ; while ( root != NULL ) { temp = root -> next ; free ( root ) ; root = temp ; } }