Nannette Bibby - Computer Science - Miami Dade College
A C++ PROGRAM THAT PRODUCES A
MINIMAL CONNECTION FOR ANY NUMBER OF CITIES
//This program finds a minimal connecting network for a set of cities
#include<iostream>
#include<string>
#include<conio.h>
using namespace std;
int main()
{
//declare variables and arrays
int citynum=0;
int connections=0;
int item[100]; //declare an array item of 100 components
string city[100]; //declare an array item of 100 components
int sum=0;
int counter=0; //loop variable control
cout<<"Enter the number of cities."<<endl;
cin>>citynum;
connections=citynum*(citynum-1)/2;
cout<<"Enter the "<<connections<<" connections"<<endl;
//Filling parrallel arrays
for(counter = 0; counter < connections; counter++)
{
cin>>city[counter];
}
for(counter = 0; counter < connections; counter++)
{
cout<<"Enter a distance for "<<city[counter]<<endl;
cin>>item[counter];
}
//Sequential sorting of arrays
//a. Find the location, smallestIndex, of the smallest element in list[index]...list[length].
//b. Swap the smallest element with list[index]. That is, swap list[smallestIndex] with list[index].
//declare variables
int index=0;
int smallestIndex=0;
int minIndex=0;
int temp=0;
string temp2=" ";
for(index = 0; index < connections; index++)
{
//Step a
smallestIndex = index;
for(minIndex = index + 1; minIndex < connections;minIndex++)
if(item[minIndex] < item[smallestIndex])
smallestIndex = minIndex;
//Step b
temp = item[smallestIndex];
temp2=city[smallestIndex];
item[smallestIndex] = item[index];
city[smallestIndex]=city[index];
item[index] = temp;
city[index]=temp2;
}
for(counter = 0; counter < connections; counter++)
{ city[counter];
item[counter];
}
cout<<"The numbers in descending order are: "<<endl;
//display array entries in reverse order
for(counter = connections-1; counter >= 0; counter--)
{ cout<<city[counter]<<" ";
cout<<item[counter]<<endl;
}
//declare variables
int numcity=0;
int numConnections=0;
numcity=(citynum-1)*(citynum-2)/2;
numConnections=connections-numcity;
//the minimal connecting network
cout<<"The minimal connecting network consists of"<<endl;
for(counter =numConnections-1 ; counter >= 0; counter--)
{ cout<<city[counter]<<" ";
cout<<item[counter]<<endl;
sum=sum+item[counter];//calculate total mileage
}
//display number of network connections removed
cout<<"removing the "<<numcity<<" longest distances. "<<endl;
//display mileage
cout<<"The minimal connecting network consists of: "<<sum<<" miles"<<endl;
getch();
return 0;
}