Scribd
Upload
11 views2 pages

Program 2

The document presents a C/C++ program that implements Prim's algorithm to find the Minimum Cost Spanning Tree of a connected undirected graph. It prompts the user to input the number of vertices and the cost matrix, then calculates and displays the edges included in the spanning tree along with the total cost. An example input and output are provided to illustrate the program's functionality.

Uploaded by

abhinehalove71
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
11 views2 pages

Program 2

The document presents a C/C++ program that implements Prim's algorithm to find the Minimum Cost Spanning Tree of a connected undirected graph. It prompts the user to input the number of vertices and the cost matrix, then calculates and displays the edges included in the spanning tree along with the total cost. An example input and output are provided to illustrate the program's functionality.

Uploaded by

abhinehalove71
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Program 2

Design and implement C/C++ Program to find Minimum Cost Spanning Tree
of a given connected undirected graph using Prim's algorithm.

#include<stdio.h>
int n,c[20][20],i,j,visited[20];
void prim();

void main()
{
printf("enter the no of vertices\n");
scanf("%d",&n);
printf("enter the cost matrix\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
scanf("%d",&c[i][j]);
visited[i]=0;
}
prim();
}

void prim()
{
int min,b,a,count=0,cost=0;
min=999;
visited[1]=1;
while(count<n-1)
{
min=999;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(visited[i]&&!visited[j]&&min>c[i][j])
{
min=c[i][j];
a=i;
b=j;
}
printf("%d->%d=%d\n",a,b,c[a][b]);
cost+=c[a][b];
visited[b]=1;
count++;
}
printf("\n total cost of spanning tree is %d",cost);
}

Sample Input and Output:


enter the no of vertices
4
enter the cost matrix
999 1 5 2
1 999 999 999
5 999 999 3
2 999 3 999
1->2=1
1->4=2
4->3=3

total cost of spanning tree is 6

You might also like