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:

The first line is the number of vertices while the other lines list out the adjacency matrix.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

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?