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 : 16 Comments

Simillar Posts

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

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

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

  2. Jaee says:
    May 1, 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 says:
    July 26, 2011 at 12:02 pm

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

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

    absolutely wrong program…

  5. ruchi sharma says:
    August 31, 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 says:
    November 1, 2011 at 10:21 pm

    yea.. its ryt

  7. lub says:
    December 9, 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 says:
    December 15, 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 says:
    December 18, 2011 at 10:32 pm

    This is wrong Program

  10. anu thomas says:
    March 20, 2012 at 4:34 pm

    u had done a great work…………….god bless u……………………..

  11. sud says:
    April 5, 2012 at 11:33 am

    thanks for the programs.

  12. DHARM DAS says:
    April 30, 2012 at 9:58 pm

    error in the program

  13. bashuka says:
    May 3, 2012 at 8:16 pm

    yes doesnt work! its working wrong.

  14. bashuka says:
    May 3, 2012 at 8:17 pm

    something like 1 2 2 2 !

  15. dhanalakshmi says:
    May 4, 2012 at 4:41 pm

    what is namespace std?
    why your use cost[i][j]=31999;
    why your not find the total minimum cost?
    i want total cost.

  16. Ummar says:
    May 7, 2012 at 11:34 pm

    this program is not working correctly..
    this program is not visiting all the nodes/vertices which a spanning tree must.

Leave a Reply

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

Free email signup