Prim.c

1. include <stdio.h>
2. include <stdlib.h>
3. include <string.h>
4. define IN_FILE "matrix.in"

1. define MAX_INT 0x7FFFFFFF

typedef struct {

   int node_count;
   int ** matrix;

} graph;

void dump_matrix(graph * my_graph){

   int i, j;
   for(i=0; i<my_graph->node_count; i++){
       for(j=0; j<my_graph->node_count; j++){
           printf("%d ", my_graph->matrix[i][j]);
       }
       printf("\n");
   }

}

graph* read_matrix(){

   FILE* input_file = fopen(IN_FILE, "r");
   if(input_file == NULL){
       printf("Error opening input file!\n");
       exit(0);
   }
   
   graph * new_graph = (graph*)malloc(sizeof(graph));
   
   fscanf(input_file, "%d", &new_graph->node_count);
   printf("Node count is %d\n", new_graph->node_count);
   
   new_graph->matrix = (int **)malloc(sizeof(int *) * new_graph->node_count);
   int i, j;
   for(i=0; i<new_graph->node_count; i++){
       new_graph->matrix[i] = (int *)malloc(sizeof(int) * new_graph->node_count);
   }
   
   for(i=0; i<new_graph->node_count; i++){
       for(j=0; j<new_graph->node_count; j++){
           fscanf(input_file, "%d", &(new_graph->matrix[i][j]));
       }
   }
   
   return new_graph;

}

graph * prim(graph * my_graph){

   graph * mst = (graph*)malloc(sizeof(graph));
   mst->node_count = my_graph->node_count;
   
   mst->matrix = (int **)malloc(sizeof(int *) * mst->node_count);
   int i, j;
   for(i=0; i<mst->node_count; i++){
       mst->matrix[i] = (unsigned char *)malloc(sizeof(int) * mst->node_count);
       memset(mst->matrix[i], 0, sizeof(int) * mst->node_count);
   }
   
   int *visited_nodes = (int*)malloc(mst->node_count * sizeof(int));
   memset(visited_nodes, 0, mst->node_count * sizeof(int));
   visited_nodes[0] = 1;
   int visited_node_count = 1;
   while(visited_node_count < mst->node_count){
       int i, j;
       int source_visited_node = 0;
       int next_visited_node = 0;
       int shortest_edge = MAX_INT;
       for(i=0; i<my_graph->node_count - 1; i++){
           for(j=i+1; j<my_graph->node_count; j++){
               if(my_graph->matrix[i][j] < shortest_edge){
                   if(visited_nodes[i] == 1 && visited_nodes[j] == 0){
                       next_visited_node = j;
                       source_visited_node = i;
                       shortest_edge = my_graph->matrix[i][j];
                   }
                   if(visited_nodes[j] == 1 && visited_nodes[i] == 0){
                       next_visited_node = i;
                       source_visited_node = j;
                       shortest_edge = my_graph->matrix[i][j];
                   }
               }
           }
       }
       
       mst->matrix[next_visited_node][source_visited_node] = shortest_edge;
       mst->matrix[source_visited_node][next_visited_node] = shortest_edge;
       visited_nodes[next_visited_node] = 1;
       visited_node_count++;
   }
   
   return mst;

}

int main(){

   graph * my_graph;
   
   my_graph = read_matrix();

   graph * mst_my_graph = prim(my_graph);
   
   dump_matrix(mst_my_graph);

   return 0;

}