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