Depth First Search with a goal state

Question

I am trying to implement depth first search on a simple graph that looks like this:

10
4 8 10
9 6 10 7 2
1 6 2 3 7
7 2 9 1 5
3 6 1 5
8 5 4
5 3 8 7
6 1 3 9
2 7 1 9
10 4 9

The first line is the number of vertices, and the other lines show the adjacency matrix.

I have code that puts the graph into an adjacency matrix. That code looks like this:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// A structure to represent an adjacency list node 
struct AdjListNode 
{ 
    int dest;
    int visited;
    struct AdjListNode* next; 
}; 

// A structure to represent an adjacency list 
struct AdjList 
{ 
    struct AdjListNode *head;  
}; 

struct Graph 
{ 
    int V;
    int dest;

    struct AdjList* array; 
}; 

// A utility function to create a new adjacency list node 
struct AdjListNode* newAdjListNode(int dest) 
{ 
    struct AdjListNode* newNode = 
     (struct AdjListNode*) malloc(sizeof(struct AdjListNode)); 
    newNode->dest = dest; 
    newNode->visited = 0;
    newNode->next = NULL; 
    return newNode; 
} 

struct Graph* createGraph(int V) 
{ 
    struct Graph* graph =  
        (struct Graph*) malloc(sizeof(struct Graph)); 
    graph->V = V; 

    // Create an array of adjacency lists.  Size of  
    // array will be V 
    graph->array =  
      (struct AdjList*) malloc(V * sizeof(struct AdjList)); 

    // Initialize each adjacency list as empty by  
    // making head as NULL 
    int i; 
    for (i = 0; i < V; ++i) 
        graph->array[i].head = NULL; 

    return graph; 
} 

// Adds an edge to an undirected graph 
void addEdge(struct Graph* graph, int src, int dest) 
{ 
    // Add an edge from src to dest.  A new node is  
    // added to the adjacency list of src.  The node 
    // is added at the begining 
    struct AdjListNode* newNode = newAdjListNode(dest); 
    newNode->next = graph->array[src].head; 
    graph->array[src].head = newNode; 


    /*

    // Since graph is undirected, add an edge from 
    // dest to src also 
    newNode = newAdjListNode(src); 
    newNode->next = graph->array[dest].head; 
    graph->array[dest].head = newNode; 
    */
}

// A utility function to print the adjacency list  
// representation of graph 
void printGraph(struct Graph* graph) 
{ 
    int v; 
    for (v = 0; v < graph->V; ++v) 
    { 
        struct AdjListNode* pCrawl = graph->array[v].head; 
        printf("\n Adjacency list of vertex %d\n head ", v); 
        while (pCrawl) 
        { 
            printf("-> %d", pCrawl->dest); 
            pCrawl = pCrawl->next; 
        } 
        printf("\n"); 
    } 
} 

int main()  
{

   char c[1000];
   FILE *fptr;


  if ((fptr = fopen("/path/to/file/small_graph.txt", "r")) == NULL)
  {
        printf("Error! opening file");
        // Program exits if file pointer returns NULL.
        exit(1);         
  }

   fscanf(fptr, "%[^\n]",c);
   printf("\n %s",c);

   int no_vertices = atoi(c);
   no_vertices = no_vertices+1;

   struct Graph* graph =createGraph(no_vertices);

   const size_t line_size = 300;
   char* line = malloc(line_size);

   for(int i = 0; i<=no_vertices; i++){
        //fscanf(fptr,"%[^\n]",c);
        //printf("\n %s", c);

        fgets(line, line_size, fptr);
        printf(line);
        char* token = strtok(line, " ");
        int start_vertex = atoi(token);
        while (token){
            printf("token: %s\n", token);
            token = strtok(NULL,  " ");
            if(token != NULL){
                int dest_vertex = atoi(token);
                addEdge(graph, start_vertex, dest_vertex);
            }


        }
   }
   printGraph(graph);
   //set_mark_to_zero(graph,2);
   do_dfs(graph->array[1],5,10,graph);
   return 0;
}

The issue that I'm running into is with my searching algorithm. I followed the pseudocode pretty accurately I'd say and I've implemented the following function:

void visit(struct AdjListNode* node){
    printf("\n%5d", node->dest);
}
void do_dfs(struct AdjList list, int goal, int no_vertices,struct Graph* graph){

    struct AdjListNode* node = list.head;
    node->visited = 1;
    visit(node);
    while(node->dest != goal){
        if(node->visited != 1){
            do_dfs(graph->array[node->dest], goal, no_vertices, graph);
        }
        node = node->next;
    }


}

The issue is that I get a seg fault and the graph just repeats the same answers. Is there a way to fix this so that depth first search works without seg faulting? The algorithm is only repeating the values 7,5,9 over and over again. Any help would be appreciated.

Answer 1

Regarding your program, you are running a recursive function without a explicit stop condition. Regarding your algorithm, I think you are not actually checking the node, but the directed segment to the node being visited. This is confusing.

First, the algorithm:

struct AdjListNode 
{ 
    int dest;
    int visited;
    struct AdjListNode* next; 
}; 

You should probably replaced dest by a pointer to a structure node. Each segment might share this pointer, and you could set this structure to visited.

struct node
{
   int value;
   int visited;
}

struct AdjListNode 
{ 
    struct node *dest;
    int visited;
    struct AdjListNode* next; 
}; 

And now, your segfault:

This reworked version of your algorithm should solve this issue. Note that I did not integrate the change I suggested in the previous section.

void visit(struct AdjListNode* node){
    printf("\n%5d:%d", node->dest, node->visited);
}

int do_dfs(struct AdjList list, int goal, int no_vertices,struct Graph* graph){

    struct AdjListNode* node = list.head;
    while(node){
        if (node->dest == goal)
        {
            visit(node);
            printf("\ndone\n");
            return (1);
        }
        if(node->visited != 1){
            visit(node);
            node->visited = 1;
            if (do_dfs(graph->array[node->dest], goal, no_vertices, graph) == 1)
              return (1);
        }
        node = node->next;
    }
    return (0);
}