BFS in C, how to get just the path to the goal?

I have a program in C that does BFS to search for a goal vertex. The problem is that it spits out all the vertices it visited and not just the path to the goal. I can't quite come up with a solution for it without causing segmentation faults.

Suppose the input file is:

Code:

---

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 while the other lines list out the adjacency matrix.

Output comes out as 1--7--3--2--6--5--9--8--10 when searching for 10 when I just want to save the path 1--7--9--10. Can anyone recommend some new data structures so that I can change this path? What I have tried doesn't work.

Code:

---

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




#define PATH_MAX 4096
int edges_visited;


struct bfs {
        struct AdjList* path;
        struct Node* next;
};
//struct bfs paths[1000];




struct AdjList {
        int value;
        int mark;
        struct Node* list;
};
struct Node {
        struct AdjList* vertex;
        struct Node* next;
};
struct Queue {
};
typedef struct AdjList AdjList;
typedef struct Node Node;
// creates a new vertex and return pointer to it
AdjList* new_vertex(int value, AdjList* graph[]) {
        AdjList* vertex = (AdjList*)malloc(sizeof(AdjList));
        vertex->value = value;
        vertex->list = 0;
        graph[value] = vertex;
        return vertex;
}
// connect vertex a to vertex b
// by adding b to a's list
void do_connect(AdjList* a, AdjList* b) {
        Node* node = (Node*)malloc(sizeof(Node));
        node->vertex = b;
        node->next = a->list;
        a->list = node;
}


// connects a to b and b to a
void connect(AdjList* a, AdjList* b) {
        do_connect (a, b);
        //do_connect (b, a);
}


// visit function
int visit(AdjList* vertex, int goal) {
        if (vertex->value == goal) {
                printf ("%d ", vertex->value);
                //clock_t end = clock();
                //time_spent += (double)(end - begin) / CLOCKS_PER_SEC;


                //printf("Time elpased is %f seconds", time_spent);
                return 1;
                //exit(0);
        }
        printf ("%d --" ,vertex->value);
       
        //return 0;
}
int do_bfs(AdjList *vertex, int* count, int goal) {
        Node *initialQueue, *front, *rear, *p, *temp;


        //struct bfs paths[1000];


        ///int path_i = 0;
        //paths[path_i].path = vertex;


        AdjList *w;
        // mark vertex with count
        vertex->mark = ++(*count);
        visit (vertex, goal);


        // initialize queue with a vertex
        initialQueue = (Node*)malloc(sizeof(Node));
        initialQueue->vertex = vertex;
        initialQueue->next = 0;
        front = initialQueue;
        rear  = initialQueue;
        // while queue is not empty
        while (front != 0) {
                // for vertex w in V adjacent to the front vertex
                p = front->vertex->list;
                while (p != 0) {
                        w = p->vertex;
                       
                        // if w is marked with 0
                        if (w->mark == 0) {
                                // paths[path_i].next = w->list;
                                // path_i++;
                                Node* nextQueue;
                                // count = count + 1, mark w with count
                                edges_visited = edges_visited+1;
                                w->mark = ++(*count);
                                int is_goal = visit (w,goal);
                                if(is_goal == 1){
                                        return path_i;
                                }
                                // add w to queue
                                nextQueue = (Node*)malloc(sizeof(Node));
                                nextQueue->vertex = w;
                                nextQueue->next = 0;
                                rear->next = nextQueue;
                                rear = nextQueue;
                        }


                        p = p->next;
                        //paths[path_i].path = p->vertex;


                }
                // remove front vertex from queue
                temp = front;
                front = front->next;
                free (temp);
        }
}
int bfs(AdjList *graph[], int goal, int no_vertices) {
        int i;
        int count = 0;
        // set all to unvisited
        for (i = 0; i < no_vertices; i ++) {
                graph[i]->mark = 0;
        }
        // do bfs for each vertex
        i = do_bfs (graph[1], &count, goal);
        return i;
}
int main(int argc, char *argv[]) {


        char c[1000];
    FILE *fptr;
    int is_bfs = 0;
    int is_dfs = 0;
    int is_extended = 0;
    int goal_vertex;
    char *graph_file;


    for(int i = 0; i< argc; i++){
            if (strcmp("-dfs", argv[i]) == 0) {
                        is_dfs = 1;       
                }       
                if (strcmp("-bfs", argv[i]) == 0) {
                        is_bfs = 1;       
                }
                if (strcmp("-dest", argv[i]) == 0) {
                        goal_vertex = atoi(argv[i+1]);
                }
                if (strcmp("-e", argv[i]) == 0) {
                        is_extended = 1;
                }
    }


    graph_file = argv[argc-1];
    //printf("\n Graph file name is: %s", graph_file);
   
    //printf("\n file path name is: %s", file_string);
   
    if ((fptr = fopen(graph_file, "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;


    AdjList *graph[no_vertices];
    for(int i = 0; i<=no_vertices; i++){
            new_vertex(i, graph);
    }


    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);
                              connect(graph[start_vertex], graph[dest_vertex]);
                          }
                  }
    }
    //printGraph(graph, no_vertices);
        double time_spent = 0.0;
        clock_t start,end;


        if (is_dfs == 1){
                // do depth first search
                printf ("path: ");
               
                start = clock();
                dfs (graph, goal_vertex, no_vertices);
                end = clock();
        }
        int path_i = 0;
        if (is_bfs == 1) {
                // do breadth first search
                printf ("\n\n");
                start = clock();


                printf ("path: ");
                path_i = bfs (graph, goal_vertex, no_vertices);
                end = clock();


        }
        time_spent = ((double) (end-start))/CLOCKS_PER_SEC;
        double time_spent_ms = time_spent * 1000000;
        printf("\nEdges: %d", edges_visited);
        printf("\nExecution time: %f ms \n", time_spent_ms);


        // printf("\n%d", path_i);
        // printf("\n%d",paths[0].path->value);


        fflush( stdout );
}

---

Any suggestions?

> Output comes out as 1--7--3--2--6--5--9--8--10 when searching for 10 when I just want to save the path 1--7--9--10.
...
> printf ("%d --" ,vertex->value);
I can recommend that you run the code in the debugger, put a breakpoint on this line and run the code.
When you get to vertex->value == 3, then you stop and have a really good think about
a) how you got to this point.
b) how to prevent getting to this point.

Oh, and you need to put back the return 0; in the visit() function as well.