Scribd
Upload
1 views4 pages

Prim

The document implements Prim's Algorithm to find the Minimum Spanning Tree (MST) of a graph. It includes functions for reading graph data, executing the algorithm, and displaying the edges of the MST along with their costs. The output demonstrates the algorithm's functionality with a sample graph of 6 nodes and 8 edges, resulting in a minimum spanning tree cost of 15.

Uploaded by

sameerkans92
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
1 views4 pages

Prim

The document implements Prim's Algorithm to find the Minimum Spanning Tree (MST) of a graph. It includes functions for reading graph data, executing the algorithm, and displaying the edges of the MST along with their costs. The output demonstrates the algorithm's functionality with a sample graph of 6 nodes and 8 edges, resulting in a minimum spanning tree cost of 15.

Uploaded by

sameerkans92
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
You are on page 1/ 4

//AIM:Implementation of Prim's Algorithm

#include<stdio.h>

#include<conio.h>

const int maxint=32767;

void readgraph(int adj[10][10],int e)

int i,j,s,d;

printf("Enter the cost of each edge of graph.....\n");

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

printf("Enter the source and desestination node:");

scanf("%d%d",&s,&d);

printf("Enter cost of edge :");

scanf("%d",&adj[s][d]);

adj[d][s]=adj[s][d];

void primst(int adj[10][10],int visited[10],int n)

int i,j,nd,min,ss,sd,x,y;

int cost=0;

visited[1]=1;

nd=1;

while(nd<n)

{
for(i=1,min=maxint;i<=n;i++)

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

if(adj[i][j]<min)

if(visited[i]!=0)

min=adj[i][j];

x=ss=i;

y=sd=j;

if(visited[ss]==0 || visited[sd]==0)

printf("Edge of MST %d:{%d-%d} and cost =%d\n",nd++,x,y,min);

cost+=min;

visited[y]=1;

adj[x][y]=adj[y][x]=maxint;

printf("Minimum cost of given Spanning Tree =%d",cost);

void main()

int adj[10][10],visited[10],i,j,n,eg;

clrscr();

printf("Enter the total no. of nodes of graph:");

scanf("%d",&n);

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

visited[i]=0;
for(i=1;i<=n;i++)

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

adj[i][j]=maxint;

printf("Enter total no. of edges of graph:");

scanf("%d",&eg);

readgraph(adj,eg);

primst(adj,visited,n);

getch();

/*OUTPUT:

Enter the total no. of nodes of graph:6

Enter total no. of edges of graph:8

Enter the cost of each edge of graph.....

Enter the source and desestination node:1 2

Enter cost of edge :5

Enter the source and desestination node:1 5

Enter cost of edge :9

Enter the source and desestination node:1 3

Enter cost of edge :8

Enter the source and desestination node:2 3

Enter cost of edge :3

Enter the source and desestination node:3 4

Enter cost of edge :7

Enter the source and desestination node:4 6


Enter cost of edge :2

Enter the source and desestination node:5 6

Enter cost of edge :1

Enter the source and desestination node:5 3

Enter cost of edge :4

Edge of MST 1:{1-2} and cost =5

Edge of MST 2:{2-3} and cost =3

Edge of MST 3:{3-5} and cost =4

Edge of MST 4:{5-6} and cost =1

Edge of MST 5:{6-4} and cost =2

Minimum cost of given Spanning Tree =15 */

You might also like