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

1. ## 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 Node* next;
};
//struct bfs paths[1000];

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

// connects a to b and b to a
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;

// 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;
}
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;

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) {
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?

2. > 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.