This is almost complete, but for some reason it is not updating the unchanged rows to visited if the values in the cost column do not change. Any ideas?
Code:
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]){
int size, i, j, k, matrix_length, prims_length, row, column;
int *matrix, *prims;
FILE *infile;
infile = fopen("prog5.in", "r");
fscanf(infile, "%d", &size);
matrix = (int *)malloc(size*size*sizeof(int)); /*Create an array of
integers large enough to
hold the matrix*/
prims = (int *)calloc(size*3,sizeof(int)); /*Create an array of
integers large enough to
hold Prim's 3 column chart
and sets initial to 0*/
matrix_length = size*size; /*gets the length of the
matrix array*/
prims_length = size*3; /*gets the length of the
matrix array*/
while(!feof(infile)){ /*while End of File is not
true*/
for(i=0; i<matrix_length; i++){
fscanf(infile, "%d", &matrix[i]); /*fills the matrix array*/
}/*for(i=0; i<length; i++){...*/
}/*while(!feof(infile)){...*/
fclose(infile); /*close the infile*/
row = 0; /*initialize row to zero*/
for(i=0; i < size; i++){
prims[3*row] = 1; /*update the visited status
of the current row*/
for(column = 0; column < size; column++){
if(matrix[(size*row)+column] > 0){
/*checks to see if the current
row is connected to the column*/
if(matrix[(size*row)+column] < prims[(3*row)+1]){
/*if the weight of the connection
is less than what is recorded*/
prims[(3*column)+1] = matrix[(size*row)+column];
prims[(3*column)+2] = row;
/*change the weight in prims to
match and set previous row to
current row*/
}else if(prims[(3*row)+1] == 0){
/*if the recorded weight is zero*/
prims[(3*column)+1] = matrix[(size*row)+column];
prims[(3*column)+2] = row;
/*change the weight in prims to
match and set previous row to
current row*/
}/*else if(prims[(3*row)+1] == 0){...*/
}/*if(matrix[size*row+column] != 0){...*/
}/*for(column = 1; column < size; column++){...*/
for(j=0; j<size; j++){
if(prims[3*j] == 0){ /*if the row isn't visited*/
for(k=0; k<size; k++){
if(prims[3*k] == 0 && k!=j){ /*if the row is being compared to itself*/
if(prims[3*j+1]<prims[3*k+1]){ /*if the cost is less than the row being compared to*/
row = j;
}/*if(prims[3*j+1]<prims[3*k+1]){...*/
}/*else if(prims[3*k] == 0){...*/
}/*for(k=0; k<size; k++){...*/
}/* if(prims[3*j] == 0){...*/
}/*for*/
for(j=0; j<prims_length; j=j+3){
printf("%d %d %d\n", prims[j],prims[j+1],prims[j+2]);
}/*for(j=0; j<prim_length; j=j+3){...*/
printf("\n");
}/*while(i=0; i<size; i++){...*/
free(matrix);
free(prims);
return 0;
}/*int main(int argc, char *argv[]){...*/
Code:
prog5.in
4
0 1 3 4
1 1 2 2
3 2 0 2
4 2 2 0
Code:
output
1 0 0
0 1 0
0 3 0
0 4 0
1 0 0
0 2 2
1 3 0
0 2 2
1 0 0
0 2 2
1 3 0
0 2 2
1 0 0
0 2 2
1 3 0
0 2 2