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

6. Implement all the functions of a dictionary (ADT) using hashing.Data: Set of (key, value) pairs, Keys are mapped to values, Keys must be comparable, Keys must be uniqueStandard Operations: Insert(key, value), Find(key), Delete(key)

#include<iostream> using namespace std; #define size 10 class Record { string name; long ph_num; int flag; public: Record() { name = "-"; ph_num = 0; flag = 0; } friend class Phonebook; }; class Phonebook { int capacity; int key; public: Phonebook() : capacity(0) {} void input( Record table[] ) { if( capacity == size ) { cout<<"HASH TABLE FULL !!"<<endl; return; } else { Record r; cout<<"ENTER NAME : "; getline(cin , r.name); cin.ignore(); cout<<"ENTER TELEPHONE NO. : "; cin>>r.ph_num; int index = hash(r.name); while(table[index].flag == 1) { if(table[index].name == r.name) { cout<<" RECORD ALREADY EXIST !!"<<endl; return; } index++; index %= size; } table[index] = r; table[index].flag = 1; capacity++; } } int hash( string name) { int sum = 0; for(int...
Read more