Computer Science: 5th sem ADA Lab Program 8

Analysis and Design of Algorithms Lab.

Question 8.

//Find the mimimum cost spanning tree of a given undirected graph using Kruskal's algorithm

#include <iostream>

#include <conio.h>

#define MAX 10

using namespace std;

void kruskal(int graph[MAX][MAX],int n)

{

int *vis=new int[n];

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

vis[i]=-1;

int edge=1,max=0;

while(edge<n)

{

int min=999,a,b,u,v;

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

{

for(int j=0;j<n;j++)

{

if(graph[i][j]<min && i!=j)

{

min=graph[i][j];

a=u=i;b=v=j;

}

}

}



while(vis[a]!=-1)

a=vis[a];

while(vis[b]!=-1)

b=vis[b];



if(a!=b)

{

vis[b]=a;

cout<<"\n"<<u<<"-"<<v<<"="<<min;

edge++;

max+=min;

}

graph[u][v]=999;

graph[v][u]=999;

}

cout<<"\nMax cost:"<<max;

}

void main()

{

cout<<"Enter the number of verticies:";

int n;cin>>n;

cout<<"Enter the weighted matrix:\n";

int graph[MAX][MAX];

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

for(int j=0;j<n;j++)

cin>>graph[i][j];

kruskal(graph,n);

getch();

}