Thread: 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?