Computer Science: 5th sem ADA Lab Program 12

Analysis and Design of Algorithms Lab.

Question 12.


//Find the minimum cost spanning tree of a given undirected graph using prim's algorithm.

#include <iostream>
#include <conio.h>

#define MAX 10

using namespace std;

void kruskal(int graph[MAX][MAX],int n,int source)
{
int *vis=new int[n];
for(int i=0;i<n;i++)
vis[i]=-1;

int edge=1,max=0;
vis[source]=0;

while(edge<n)
{
int min=99,u,v;

for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
if(i!=j && graph[i][j]<min && (vis[i]==-1 || vis[j]==-1) && !(vis[i]==-1 && vis[j]==-1))
{
min=graph[i][j];
u=i;v=j;
}
}

vis[v]=u;
cout<<"\n"<<u+1<<"-"<<v+1<<"="<<min;
edge++;
max+=min;
graph[u][v]=99;
graph[v][u]=99;
}

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

void main()
{
cout<<"Enter the number of verticies:";
int n;cin>>n;

cout<<"Enter the source:";
int source;cin>>source;

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,source);
getch();
}