kruskals algorithm for Graph implementation in c

Kruskals algorithm first sort all the edge weights in ascending order and then starting from the smallest weighted edge to create a minimum spanning tree or minimal spanning tree .it is easiiest and best algorithm to find the minimum spanning tree .

pls dont forget to share and request for other codes in the comments section

 

 

 

#include<stdio.h>

#include<stdlib.h>

typedef struct node


int v1,v2;

int w;

edge;

edge e[10];

int nv,ne;

int parent[10];

int tree[10][3];

void InputGraph()


FILE *fp;

fp=fopen(“kruskal.txt”,”r”);

if(fp==NULL)


printf(“FAILED TO OPEN THE FILE.”);

return;


fscanf(fp,”%d”,&nv);

fscanf(fp,”%d”,&ne);

int i;

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


fscanf(fp,”%d”,&e[i].v1);

fscanf(fp,”%d”,&e[i].v2);

fscanf(fp,”%d”,&e[i].w);


fclose(fp);

return;


void DisplayGraph()


int i;

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

printf(“(%d,%d)->%d”,e[i].v1,e[i].v2,e[i].w);

printf(“\n”);



void sort()


int i,j;

edge temp;

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


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


if(e[i].w>e[j].w)


temp=e[i];

e[i]=e[j];

e[j]=temp;

void MakeSet(int v)

parent[v]=-1;


int FindSet(int x)


while(parent[x]>=0)x=parent[x];

return x;


void Union(int x,int y)


parent[y]=x;

return;


int treeedge;

void Krushkal()


int i;

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

MakeSet(i);

sort();

int k=1;

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

if(FindSet(e[i].v1)!=FindSet(e[i].v2))

tree[k][1]=e[i].v1;

tree[k][2]=e[i].v2;

k++;

Union(e[i].v1,e[i].v2);



k–;

treeedge=k;


void DisplayTree()

int i;

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

printf(“%d->%d\n”,tree[i][1],tree[i][2]);

return;


int main()


InputGraph();

DisplayGraph();

Krushkal();

printf(“—————\n”);

DisplayTree();

return 0;

kruskals algorithm for Graph implementation in c