Diferență între revizuiri ale paginii „Prim.c”

De la WikiLabs
Jump to navigationJump to search
(Pagină nouă: <syntaxhighlight lang="c"> #include <stdio.h> #include <stdlib.h> #include <string.h> #define IN_FILE "matrix.in" #define MAX_INT 0x7FFFFFFF typedef struct { int node_count; ...)
 
Linia 1: Linia 1:
<syntaxhighlight lang="c">
 
 
#include <stdio.h>
 
#include <stdio.h>
 
#include <stdlib.h>
 
#include <stdlib.h>
Linia 9: Linia 8:
 
typedef struct {
 
typedef struct {
 
     int node_count;
 
     int node_count;
     unsigned char ** matrix;
+
     int ** matrix;
 
} graph;
 
} graph;
  
Linia 35: Linia 34:
 
     printf("Node count is %d\n", new_graph->node_count);
 
     printf("Node count is %d\n", new_graph->node_count);
 
      
 
      
     new_graph->matrix = (unsigned char **)malloc(sizeof(unsigned char *) * new_graph->node_count);
+
     new_graph->matrix = (int **)malloc(sizeof(int *) * new_graph->node_count);
 
     int i, j;
 
     int i, j;
 
     for(i=0; i<new_graph->node_count; i++){
 
     for(i=0; i<new_graph->node_count; i++){
         new_graph->matrix[i] = (unsigned char *)malloc(sizeof(unsigned char) * new_graph->node_count);
+
         new_graph->matrix[i] = (int *)malloc(sizeof(int) * new_graph->node_count);
 
     }
 
     }
 
      
 
      
Linia 54: Linia 53:
 
     mst->node_count = my_graph->node_count;
 
     mst->node_count = my_graph->node_count;
 
      
 
      
     mst->matrix = (unsigned char **)malloc(sizeof(unsigned char *) * mst->node_count);
+
     mst->matrix = (int **)malloc(sizeof(int *) * mst->node_count);
 
     int i, j;
 
     int i, j;
 
     for(i=0; i<mst->node_count; i++){
 
     for(i=0; i<mst->node_count; i++){
         mst->matrix[i] = (unsigned char *)malloc(sizeof(unsigned char) * mst->node_count);
+
         mst->matrix[i] = (unsigned char *)malloc(sizeof(int) * mst->node_count);
         memset(mst->matrix[i], 0, sizeof(unsigned char) * mst->node_count);
+
         memset(mst->matrix[i], 0, sizeof(int) * mst->node_count);
 
     }
 
     }
 
      
 
      
Linia 107: Linia 106:
 
     return 0;
 
     return 0;
 
}
 
}
</syntaxhighlight>
 

Versiunea de la data 10 mai 2014 08:20

  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;

}