8. Prims Algorithm 

#include<iostream>
using namespace std;
#define infi 9999;

class prim
{
	float arr[10][10];
	int nodes;
	char a[6] = {'A','B','C','D','E','F'};
	
public:

	void creategraph()
	{
		cout<<"ENTER THE NUMBER OF NODES : ";
		cin>>nodes;
		
		for( int i = 0 ; i < nodes  ; i++ )
		{	
			for( int j = 0 ; j < nodes ; j++)
			{
				if( i != j && i < j )
				{
					cout<<"DISTANCE BETWEEN "<<a[i]<<" TO "<<a[j]<<" = ";
					cin>>arr[i][j];
					arr[j][i] = arr[i][j];
				}
				else if(i == j)
				{
					arr[i][j] = 0;
				}
			}
		}
		for(int i = 0 ; i < nodes ; i++)
			for(int j = 0 ; j < nodes ; j++)
				if( arr[i][j] == 0 )
					arr[i][j] = infi; 
	}
	
	void primalgo()
	{
		creategraph();					// call to creategraph 
		int visited[nodes];				// defines which nodes are visited and from these nodes we need to find the minimum path
		float min = 0, ne = 0;			//minimun to find the minimum edge from the nodes and ne = number of edges 
		int x,y,i,j;					// i and j loop variables. x and y to store value of i and j where min values occur in graph
		float cost = 0;					// Store minimum cost
		
		// Initially no node is visited 		
		for( int i = 0 ; i < nodes ; i++)
		{
			visited[i] = 0;
		}
		
		//visiting 1st node
		visited[0] = 1;
		
		// Number of edges in a Minimum Spanning Tree is nodes - 1
		while( ne < nodes - 1)	
	 	{
	 		min = infi;			// inorder to find minimum value or else min = 0 will always be the min.
	 		
	 		//loop for all the visited node so we determine minimum distance from all visited node
	 		for(int i = 0 ; i < nodes ; i++)
	 		{
	 			if( visited[i] == 1)
	 			{
	 				//loop for all the un-visited node so we determine the node to be visited next to get minimum dist.
	 				for(int j = 0 ; j < nodes ; j++)
	 				{
	 					if( visited[j] == 0)
	 					{
	 						if( min > arr[i][j] )
	 						{
	 							min = arr[i][j];
	 							x 	= i;
	 							y	= j;
 							}
						}
					}
				}
			}
			visited[y] = 1;
			cost += min;
			ne++;
			cout<<a[x]<<"-->"<<a[y]<<endl;
		}
		cout<<endl<<"MINIMUM COST = "<<cost<<endl;
	}
};

int main()
{
	prim p;
	p.primalgo();
	return 0;
}

Comments

Post a Comment

Popular posts from this blog

2. Beginning with an empty binary search tree, Construct binary search tree by inserting the values in the order given. After constructing a binary tree -i.Insert new nodeii.Find number of nodes in longest path iii.Minimum data value found inthe tree iv.Change a tree so that the roles of the left and right pointers are swapped at every node v.Search a value

#include<iostream> #include<math.h> using namespace std; struct Bstnode { int data; Bstnode *left = NULL; Bstnode *right = NULL; }; class Btree { int n; int x; int flag; public: Bstnode * root; Btree() { root = NULL; } Bstnode *GetNewNode(int in_data) { Bstnode * ptr = new Bstnode(); ptr->data = in_data; ptr->left = NULL; ptr->right = NULL; return ptr; } Bstnode *insert( Bstnode *temp , int in_data) { if( temp == NULL ) { temp = GetNewNode(in_data); } else if( temp->data > in_data) { temp->left = insert(temp->left , in_data); } else { temp->right = insert( temp->right , in_data); } return temp; } void input() { cout<<"ENTER NUMBER OF ELEMENTS IN THE BST : "; cin>>n; for(int i = 0 ; i < n ; i++) { cout<<"NUMBER = "; cin>>x; root = insert(root , x); } } int search(Bstnode *temp ,int in_data) { if( te...
Read more

1. A book consists of chapters, chapters consist of sections and sections consist of subsections. Construct a tree and print the nodes. Find the time and space requirements of your method.

#include<iostream> using namespace std; struct node { string name; node *B[5]; }; class book { int c,s,sub; public: node *temp = new node; void Getnewnode() { for(int i = 0 ; i<5 ; i++) { temp->B[i] = new node; temp->B[i]->name = "empty"; for(int j=0; j<5; j++) { temp->B[i]->B[j] = new node; temp->B[i]->B[j]->name = "empty"; for(int k = 0 ; k<5; k ++) { temp->B[i]->B[j]->B[k] = new node; temp->B[i]->B[j]->B[k]->name = "empty"; } } } } void add_title() { cout<<": ENTER THE TITLE OF THE BOOK = "; cin>>temp->name; Getnewnode(); } void add_chapter() { string cname; int cnum; cout<<": ENTER NUMBER OF CHAPTERS IN THE BOOK = "; cin>>cnum; c = cnum; for(int i = 0 ; i < cnum ; i++) { cout<<endl<<"Chapter "<...
Read more

4. Write a function to get the number of vertices in an undirected graph and its edges. You may assume thatno edge is input twice. i.Use adjacency list representation of the graph and find runtime of the functionii.Use adjacency matrix representation of the graph and find runtime of the function

#include<iostream> using namespace std; class node { public: char data; node *start = NULL; node *next; void list(char ch) { node *ptr = new node; node *temp = new node; ptr->data = ch; if(start == NULL) { start = ptr; start->next = NULL; } else { temp = start; while(temp->next != NULL) { temp = temp->next; } ptr->next = NULL; temp->next = ptr; } } void displaylist() { node *temp = new node; if(start == NULL) { cout<<"LIST IS EMPTY"<<endl; } else { temp = start; while(temp != NULL) { cout<<temp->data<<"->"; temp = temp->next; } cout<<endl; } } }; class graph { int a[10][10]; char arr[5] = {'A','B','C','D','E'}; int vertices; node al[5]; public: graph() { cout<<"ENTER THE NUMBER OF VERTICES IN THE GRAPH \t::\t"; cin>>ve...
Read more