Diferență între revizuiri ale paginii „Connected graph.c”
De la WikiLabs
Jump to navigationJump to search (Pagină nouă: <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; unsigne...) |
|||
Linia 9: | Linia 9: | ||
typedef struct { | typedef struct { | ||
int node_count; | int node_count; | ||
− | unsigned char ** matrix | + | unsigned char ** matrix; |
} graph; | } graph; | ||
Versiunea curentă din 24 aprilie 2014 08:58
#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;
}