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

12. Write a Java program which will demonstrate a concept of cohesion and coupling of the various modules in the program.

 -------------------------Coupling--------------------------- import java.lang.*; import java.util.*; class Box { public int vol; Box( int l , int b , int h) { this.vol = l*b*h; } } class Volume { public static void main(String args[]) { Box b = new Box(5,5,5); System.out.println("VOLUME : " + b.vol); } }     -------------------------Cohesion--------------------------- import java.util.*; import java.lang.*; class Name { String name; public String getName(String name) { this.name = name; return name; } } class Age { int age; public int getAge(int age) { this.age = age; return age; } } class Number { int num; public int getNum(int num) { this.num = num; return num; } } public class Student { public static void main(String args[]) { Name n = new Name(); System.out.println("NAME : " + n.getName("Shreyas")); Age a = new Age(); System.out.println("Age : " + a.getAge(20)...
Read more

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

11. Any application defining scope of Formal parameter, Global parameter, Local parameter accessing mechanism and also relevance to private, public and protected access. Write a Java program which demonstrates the scope rules of the programming mechanism.

import java.util.*; class employee { public String e_name; protected int e_id; String e_add; double salary; employee() { e_name = "abc"; e_id = 0; e_add = "xyz"; salary = 0; } } class Company extends employee { private long ph_no; void get() { Scanner in = new Scanner(System.in); System.out.println("ID : "); e_id = in.nextInt(); System.out.println("NAME : "); e_name = in.next(); System.out.println("ADDRESS : "); e_add = in.next(); System.out.println("SALARY : "); salary = in.nextDouble(); System.out.println("PHONE NO. : "); ph_no = in.nextLong(); } void put() { System.out.println("ID : " + this.e_id); System.out.println("NAME : " + this.e_name); System.out.println("ADDRESS : " + e_add); System.out.println("SALARY : " + salary); System.out.println("PHONE NO. : " + ph_no); } public static void m...
Read more