/*
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;
}