Home > Source Codes > Software Programs > C++ Programs > Data structure > C++ programs to implement the Prim’s algorithm to generate a minimum cost spanning tree

C++ programs to implement the Prim’s algorithm to generate a minimum cost spanning tree

Thursday, March 11th, 2010

/* Write C++ programs to implement the Prim’s algorithm to generate a minimum cost spanning tree */

#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10],u;
 
main()
{
	int m,c;
	cout <<"enterno of vertices";
	cin >> n;
	cout <<"ente no of edges";
	cin >> m;
	cout <<"\nEDGES Cost\n";
	for(k=1;k<=m;k++)
	{
		cin >>i>>j>>c;
		cost[i][j]=c;
	}
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
		if(cost[i][j]==0)
		cost[i][j]=31999;
 
	cout <<"ORDER OF VISITED VERTICES";
	k=1;
	while(k<n)
	{
		m=31999;
		if(k==1)
		{
			for(i=1;i<=n;i++)
				for(j=1;j<=m;j++)
				if(cost[i][j]<m)
				{
					m=cost[i][j];
					u=i;
				}
		}
		else
		{
			for(j=n;j>=1;j--)
			if(cost[v][j]<m && visited[j]!=1 && visit[j]!=1)
			{
				visit[j]=1;
				stk[top]=j;
				top++;
				m=cost[v][j];
				u=j;
			}
		}
		cost[v][u]=31999;
		v=u;
		cout<<v << " ";
		k++;
		visit[v]=0; visited[v]=1;
	}
}

OUTPUT

enterno of vertices7
ente no of edges9

EDGES Cost
1 6 10
6 5 25
5 4 22
4 3 12
3 2 16
2 7 14
5 7 24
4 7 18
1 2 28
ORDER OF VISITED VERTICES1 6 5 4 3 2

Avatar Image

Author Name :
Ranjith

Total : 9 Comments

Simillar Posts

9 Responses to C++ programs to implement the Prim’s algorithm to generate a minimum cost spanning tree

  1. manpreet
    April 13th, 2011 at 2:34 pm

    why m=31999 ????
    cost[v][u]=31999 ??

  2. Jaee
    May 1st, 2011 at 5:19 pm

    When m=31999 in the beginning it ensures that when the condition for minimum weight is checked for the first time, that particular weight will be definitely less than 31999, so it will replace 31999 as the current min weight.

  3. MYTHILI
    July 26th, 2011 at 12:02 pm

    why you should assign m=31999?????

  4. vishal
    August 23rd, 2011 at 7:55 pm

    absolutely wrong program…

  5. ruchi sharma
    August 31st, 2011 at 7:17 pm

    hello……..
    i need hel of this program in my assignment so please anyone can tell me, Is this program is ok or not………..

  6. karanbir singh
    November 1st, 2011 at 10:21 pm

    yea.. its ryt

  7. lub
    December 9th, 2011 at 11:09 pm

    this program isn’t working =( show result like 1 3 5 9 9 9 9 9 or smth like that…=(
    it is working normally just for author’s example

  8. praveen
    December 15th, 2011 at 10:54 am

    @mythili
    we will take max possible cost for the edges which are not really there in graph,as cost is assigned as a datatype of int we will take max possiible value in int datatypei.e.
    31999

  9. hessar
    December 18th, 2011 at 10:32 pm

    This is wrong Program

Leave a Reply

Question and Answer
C/C++ Unix & Linux Wordpress
Source codes
C C++ Java

Free email signup