View Single Post
  #1 (permalink)  
Old June 7th, 2004, 12:51 PM
gbilios gbilios is offline
Authorized User
 
Join Date: Mar 2004
Posts: 33
Thanks: 0
Thanked 1 Time in 1 Post
Default 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
Reply With Quote