Untitled

/*
 Assignment-7 You have a business with several offices; you want to lease phone lines to connect them up with each other; and the phone
 company charges different amounts of money to connect different pairs of cities.
 You want a set of lines that connects all your offices with a minimum total cost.
 Solve the problem by suggesting appropriate data structures.
 */
#include <iostream>
#define mx 2147483647;
using namespace std;

class Graph {
	int cost[20][20];
	int near[21];
	int ST[2][20];
	int vertices;
	int edges;
public:
	Graph() {
		vertices = edges = -1;
	}
	Graph(int x, int y) {
		vertices = x;
		edges = y;
		for (int i = 0; i < 20; i++) {
			near[i] = mx;
			near[20] = mx;
			for (int j = 0; j < 20; j++) {
				cost[i][j] = mx;
			}
		}

		for(int i=0;i<20;i++){
			ST[0][i]=0;
			ST[1][i]=0;
		}

		int mini=mx;
		int minj=mx;
		int min=mx;

		for(int i=1;i<=vertices;i++){
			for(int j=i;j<=vertices;j++){
				if(i==j) continue;
				int x;
				cout<<"Enter cost between line "<<i<<" and "<<j<<": ";
				cin>>x;
				if(x==-1) continue;
				cost[i][j]=x;
				cost[j][i]=x;
				if(x<min){
					min=x;
					mini=i;
					minj=j;
				}
			}
		}
		near[mini]=0;
		near[minj]=0;
		ST[0][0]=mini;
		ST[1][0]=minj;
		int k=ST[1][0];
		int l= ST[0][0];
		for(int i=1;i<=vertices;i++){
//			if(cost[i][k]<near[i]){
//				near[i]=k;
//			}
//			if(cost[i][l]<near[i]){
//				near[i]=l;
//			}
			if(near[i]==0) continue;
			if(cost[i][k]<cost[i][l]) near[i]=k;
			else if(cost[i][k]>cost[i][l])near[i]=l;
		}
	}

	void prims(){

		int curr=0;
//		k= ST[1][curr];
//		l= ST[0][curr];

//		for(int i=1; i<=vertices;i++){
//			if(near[i]==0) continue;
//			int tmp1= cost[i][k];
//			int tmp2= cost[i][l];
//			if(tmp1<tmp2) near[i]= k;
//			else near[i]=l;
//		}
//		for(int i=0;i<vertices-1;i++){
//			int k,l;
//			int mn=mx;

//					for(int j=1;j<=vertices;j++){
//						if(near[j]!=0 && cost[j][near[j]]<mn){
//							mn=cost[j][near[j]];
//							k=j;
//						}
//					}
//					ST[0][i]=k; ST[1][i]= near[k];
//					near[k]=0;
//					for(int j=1;j<=vertices;j++){
//						if(near[j]!=0 && cost[j][k]<cost[j][near[j]]) near[j]=k;
//					}
//		}
		cout<<"H";

	}

}*G;

int main() {
	bool menu=1;
	int ch;
	int v,e;
	while(menu){
		cout<<"\n\n1.Enter graph\n2.\nEnter choice: ";
		cin>>ch;
		switch (ch) {
			case 1:
				cout<<"\nEnter vertices: "; cin>>v;
				cout<<"Enter edges: "; cin>>e;
				G= new Graph(v,e);
				G->prims();
				break;
			case -1:
				menu=0;
				break;
			default:
				break;
		}
	}
	return 0;
}