# Untitled

unknown
plain_text
2 years ago
2.5 kB
3
Indexable
Never
```/*
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;
}

```