Depth First Search
i have written an application that builds an adjacency list (directed). i have problems with my depth first function. i cant get it to work. can someone please help.
#include <stdio.h>
#include <string.h>
#include<stdlib.h>
#define LABEL_SIZE 20
#define TRUE 1
#define FALSE 0
/* structure definitions */
struct arc
{
struct node *dest_node;
struct arc *next;
};
struct node
{
char label[LABEL_SIZE];
struct arc *arc_list;
struct node *next;
short int visited;
};
struct graph
{
short int visited;
int number_of_nodes;
struct node *node_list;
};
/* function prototypes */
void initialise(struct graph *);
int empty(struct graph *);
struct node *add_node(struct graph *, char *);
struct node *get_node(struct graph *, char *);
struct arc *add_arc(struct graph *, char *, char *);
void print_node(struct node *);
void print_arc(struct arc *);
void print_graph(struct graph *);
void dfs(struct graph *);
void dfs_visit_node(struct node *);
/* function definitions */
int main()
{
struct graph graph;
initialise(&graph);
add_node(&graph, "A");
add_node(&graph, "B");
add_node(&graph, "C");
add_node(&graph, "D");
add_node(&graph, "E");
add_node(&graph, "F");
add_node(&graph, "G");
add_node(&graph, "H");
add_node(&graph, "I");
add_arc(&graph, "A", "B");
add_arc(&graph, "A", "C");
add_arc(&graph, "B", "E");
add_arc(&graph, "B", "D");
add_arc(&graph, "C", "D");
add_arc(&graph, "C", "G");
add_arc(&graph, "D", "E");
add_arc(&graph, "D", "F");
add_arc(&graph, "E", "F");
add_arc(&graph, "E", "H");
add_arc(&graph, "F", "H");
add_arc(&graph, "F", "G");
add_arc(&graph, "G", "");
add_arc(&graph, "H", "I");
add_arc(&graph, "I", "");
print_graph(&graph);
return(0);
}
void initialise(struct graph *graph)
{
/* initialise the 2 attributes of a graph */
graph->number_of_nodes = 0;
graph->node_list = NULL;
}
int empty(struct graph *graph)
{
return(graph->number_of_nodes == 0);
}
struct node *add_node(struct graph *graph, char *label)
{
/* declare a pointer for a new node */
struct node *new_node;
/* allocate and initialise a new node */
new_node = (struct node *)malloc(sizeof(struct node));
if(new_node == NULL)
{
printf("error in add_node(): malloc() failed\n");
return(NULL);
}
strcpy(new_node->label, label);
new_node->arc_list = NULL;
new_node->next = NULL;
/* insert new node into the graph's list of nodes */
new_node->next = graph->node_list;
graph->node_list = new_node;
/* increment the number of nodes */
graph->number_of_nodes++;
/* return the pointer to the new node */
return(new_node);
}
struct node *get_node(struct graph *graph, char *label)
{
struct node *node;
for(node = graph->node_list; node != NULL; node = node->next)
if(strcmp(label, node->label) == 0)
return(node);
return(NULL);
}
struct arc *add_arc(struct graph *graph,
char *source_label, char *dest_label)
{
/* declare a pointer for a new arc */
/* declare a pointer to refer to the source node */
/* declare a pointer to refer to the destination node */
struct arc *new_arc;
struct node *source_node, *dest_node;
/*
Use get_node() to get a pointer to the
source node based on the source label.
Display an error message if a node cannot be found
and also return NULL.
*/
if((source_node = get_node(graph, source_label)) == NULL)
{
printf("error: %s not found\n", source_label);
return(NULL);
}
/*
Use get_node() to get a pointer to the
destination node based on the destination label.
Display an error message if a node cannot be found
and also return NULL.
*/
if((dest_node = get_node(graph, dest_label)) == NULL)
{
/*printf("error: %s not found\n", dest_label);*/
return(NULL);
}
/* allocate and initialise a new arc */
new_arc = (struct arc *)malloc(sizeof(struct arc));
if(new_arc == NULL)
{
printf("error in add_arc(): malloc() failed\n");
return(NULL);
}
new_arc->dest_node = dest_node;
new_arc->next = NULL;
/* insert the new arc into the source node's list of arcs */
new_arc->next = source_node->arc_list;
source_node->arc_list = new_arc;
/* return the pointer to the new arc */
return(new_arc);
}
void print_node(struct node *node)
{
struct arc *arc;
printf(" %s : ", node->label);
for(arc = node->arc_list; arc != NULL; arc = arc->next)
print_arc(arc);
printf("\n");
}
void print_arc(struct arc *arc)
{
printf("(%s) ", arc->dest_node->label);
}
void print_graph(struct graph *graph)
{
struct node *node;
printf("The adjacency list for the graph is: \n");
printf(" (Graph has %d nodes)\n", graph->number_of_nodes);
for(node = graph->node_list; node != NULL; node = node->next)
print_node(node);dfs(graph);
}
void dfs(struct graph *graph)
{
int index;
struct node *node;
node = (struct node *) malloc(sizeof(struct node));
node->visited = FALSE;
/* depth first search of graph beginning with vertex node.*/
for(index = 0; index < graph->number_of_nodes; index++)
if(!node->visited)
dfs_visit_node(node);
}
void dfs_visit_node(struct node *node)
{
struct arc *arc;
arc = (struct arc *) malloc(sizeof(struct arc));
for(arc = node->arc_list; arc != NULL; arc = arc->next)
{
if(!node->visited)
dfs_visit_node(node);
}
node->visited = TRUE;
printf("Traverse graph using DFS starting from node \"A\":\n");
print_node(node);
}
__________________
gbilios
|
