Vizualizare sursă pentru „Connected graph.c”

<syntaxhighlight lang="c">
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stack.h"

#define IN_FILE "matrix.in"

typedef struct {
    int node_count;
    unsigned char ** matrix;
} graph;


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 = (unsigned char **)malloc(sizeof(unsigned char *) * new_graph->node_count);
    int i, j;
    for(i=0; i<new_graph->node_count; i++){
        new_graph->matrix[i] = (unsigned char *)malloc(sizeof(unsigned char) * 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;
}

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");
    }
}

void depth_search(graph *my_graph, struct stack * my_stack, unsigned char * visited_nodes){
    
    int i;
    while(!is_empty(my_stack)){
        unsigned char node = stack_pop(my_stack);
        stack_push(my_stack, node);
        for(i=0; i<my_graph->node_count; i++){
            if(my_graph->matrix[node][i] == 1 && visited_nodes[i] == 0){
                stack_push(my_stack, i);
                visited_nodes[i]  = 1;
                depth_search(my_graph, my_stack, visited_nodes);
            }
        }
        stack_pop(my_stack);
    }
    
}   

int main(){
    graph * my_graph;
    
    my_graph = read_matrix();

    dump_matrix(my_graph);

    unsigned char * visited_nodes = (unsigned char *)malloc(my_graph->node_count * sizeof(unsigned char *));
    memset(visited_nodes, 0, my_graph->node_count * sizeof(unsigned char *));
    
    struct stack * my_stack = create_stack(my_graph->node_count);

    stack_push(my_stack, 0);
    visited_nodes[0] = 1;
    
    depth_search(my_graph, my_stack, visited_nodes);
    int i;
    for(i=0; i<my_graph->node_count; i++){
        if(visited_nodes[i] == 0){
            printf("Graph is NOT connected!\n");
            return 0;
        }
    }   

    printf("Graph is connected!\n");
    return 0;
}
</syntaxhighlight>