Vizualizare sursă pentru „Prim.c”

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define IN_FILE "matrix.in"

#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;
}