Rhobincu la 24 aprilie 2014 08:58

2014-04-24T08:58:07Z

Rhobincu: Pagină nouă: #include #include #include #include "stack.h" #define IN_FILE "matrix.in" typedef struct { int node_count; unsigne...

2014-04-24T08:57:40Z

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...

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

@@ Linia 9: / Linia 9: @@
 typedef struct {
      int node_count;
-     unsigned char ** matrix
+     unsigned char ** matrix;
 } graph;

Connected graph.c - Revizia istoricului

Rhobincu la 24 aprilie 2014 08:58

Rhobincu: Pagină nouă: #include #include #include #include "stack.h" #define IN_FILE "matrix.in" typedef struct { int node_count; unsigne...