well i have a whole program ill post the whole thing. I have a 2d array that represents a graph. The user enters a a starting vertex (the row), ending vertex (the column) and weight all as numbers. it goes to the spot in the 2d array and puts the weight number there. This keeps going until the user enters -1 for all of them. Then it asks for a vertex to start on which would be the row and then it looks through that row and finds the smallest value. It then has to add just the row to a finishedVerteices array and then adds the smallest weight to a finishedWeight array and then makes the column it found it at the next row. Then it searches that row and keeps going until the size of the array is met. I also have to have some checks. I have to check to make sure the vertex is finds that has the smallest is not already in the finishedVertices array. I also have to adjust the weights if the next vertex has a better path to a weight. The whole thing should work except the prim function. That is the function that does the searching and adding to the other arrays. And i need a function that will print the arrays also. I have an attempt at this but can not test it because the prim function doesn't work.
Here is the code:
#include <iostream>
#include<math.h>
#import<string.h>
using namespace std;
int matrix[50][50];
int finishedWeight[50];
int finishedVertices[50];
char* edges[50];
int counter = 0;
int size = 0;
//fill the matrix with a big number
void fillMatrix(int vertexNum)
{
for(int i = 0; i < vertexNum; i++)
{
for(int j = 0; j < vertexNum; j++)
{
matrix[i][j] = pow(2,32) - 1;
}
}
}
//set the weight of the vertices
void insert(int start, int end, int weight)
{
matrix[start][end] = weight;
}
//add the edge for an undirected graph
void addUndirected(int vertexNum)
{
int start = 0;
int end = 0;
int weight;
size = vertexNum;
fillMatrix(vertexNum);
while(start != -1)
{
cout << "Please enter a starting vertex: ";
cin >> start;
cout << "Please enter an ending vertex: ";
cin >> end;
cout << "Please enter a weight: ";
cin >> weight;
insert(start, end, weight);
insert(end, start, weight);
}
for(int i = 0; i < vertexNum; i++)
{
for(int j = 0; j < vertexNum; j++)
{
cout << "matrix[" << i << "][" << j << "] = " << matrix[i][j] << endl;
}
}
}
// add the edge for a directed graph
void addDirected(int vertexNum)
{
int start = 0;
int end = 0;
int weight;
size = vertexNum;
fillMatrix(vertexNum);
while(start != -1)
{
cout << "Please enter a starting vertex: ";
cin >> start;
cout << "Please enter an ending vertex: ";
cin >> end;
cout << "Please enter a weight: ";
cin >> weight;
insert(start, end, weight);
}
for(int i = 0; i < vertexNum; i++)
{
for(int j = 0; j < vertexNum; j++)
{
cout << "matrix[" << i << "][" << j << "] = " << matrix[i][j] << endl;
}
}
}
//execute the algorithm
void prim(int startingVertex)
{
cout << "Size = " << size << endl;
int start = startingVertex;
int end;
int weight;
int minx;
int miny;
int minWeight = pow(2, 32) - 1;
for(int k = 0; k < size; k++)
{
finishedVertices[k] = start;
for(int l = 0; l < size; l++)
{
if(matrix[start][l] < minWeight)
{
for(int i = 0; i < size; i++)
{
if(matrix[start][l] != finishedVertices[i])
{
minx = start;
miny = l;
minWeight = matrix[minx][miny];
}
}
}
}
}
finishedVertices[counter] = minx;
cout << "counter = " << counter << endl;
cout << "finished vertices at 0 = " << finishedVertices[0] << endl;
cout << "finished vertices at 1 = " << finishedVertices[1] << endl;
finishedWeight[counter] = minWeight;
cout << "FinishedWeight at 0 = " << finishedWeight[0] << endl;
cout << "finishedWeight at 1 = " << finishedWeight[1] << endl;
//edges[counter] = minx + ',' + miny;
counter++;
if(counter != size)
prim(2); // this is just to test to see if another vertex would work
// really the parameter for this should be the column the lowest
// weight was in
}
void display()
{
for(int v = 0; v < size; v++)
{
cout << finishedVertices[v];
for(int w = 0; w < size; w++)
{
cout << finishedWeight[w];
}
}
}
// run functions and prompts
int main()
{
int option = 0; // option for starting vertex for algorithm
int option1 = 0; // option for directed or undirected
int option2; // option to see if the algorithm is run again
int vertexNum = 0;
while(option1 != 3)
{
option2 = 1;
cout << "1. Directed Graph. \n"
<< "2. Undirected Graph. \n"
<< "3. Exit. \n"
<< "Selection: ";
cin >> option1;
if(option1 == 1)
{
cout << "Enter the number of vertices ";
cin >> vertexNum;
addDirected(vertexNum);
while(option2 == 1)
{
cout << "Please enter a starting vertex for the algorithm ";
cin >> option;
prim(option);
cout << "Press 1 to run the algorithm with a different starting vertex or 2 to go back to the main menu ";
cin >> option2;
}
}
else if(option1 == 2)
{
cout << "Enter the number of vertices ";
cin >> vertexNum;
addUndirected(vertexNum);
while(option2 == 1)
{
cout << "Please enter a starting vertex for the algorithm ";
cin >> option;
prim(option);
cout << "Press 1 to run the algorithm with a different starting vertex or 2 to go back to the main menu ";
cin >> option2;
}
}
}
return 0;
}