# Breadth-First Search of a graph in C A breadth-first search (BFS) of a graph visits every neighbour of the current vertex before visiting the neighbours’ neighbours. This means that a breadth-first search extends radially from the starting vertex.

The algorithm is as follows:

1. Create an empty set for the visited vertices
2. Create a queue
3. Put the starting vertex in the visited set
4. Put the starting vertex in the queue
5. While the queue is not empty:
1. Remove a vertex from the queue
2. Perform any visit actions on it
3. For each of the vertex’s neighbours:
• If the neighbour is not in the visited set:
1. Put the neighbour in the visited set
2. Add the neighbour to the queue

Here is an implementation in C using a cirque for the queue. The function breadth_first_search() takes a graph in edge list form, the number of edges (size), the number of vertices (order), and a callback function that is called for each vertex visited.

#include <stdlib.h>

#include <cirque.h>

typedef struct {
unsigned int first;
unsigned int second;
} edge;

typedef void (*searchfn)(unsigned int);

void breadth_first_search(const edge *edges, unsigned int size, unsigned int order, searchfn fun)
{
unsigned int start = 0;
unsigned int *visited = calloc(order, sizeof(unsigned int));
cirque *queue = cirque_create();
if (!(visited && queue)) {
free(visited);
cirque_delete(queue);
return;
}
visited[start] = 1;
cirque_insert(queue, &start);
while (cirque_get_count(queue)) {
unsigned int e;
unsigned int *current = cirque_remove(queue);
fun(*current);
for (e = 0; e < size; e++) {
if (edges[e].first == *current || edges[e].second == *current) {
const unsigned int *neighbour = edges[e].first == *current ?
&edges[e].second : &edges[e].first;
if (!visited[*neighbour]) {
visited[*neighbour] = 1;
cirque_insert(queue, (void*)neighbour);
}
}
}
}
free(visited);
cirque_delete(queue);
}


Here is an example program that constructs the graph shown at the top and then performs a BFS on it, printing the numbers of the vertices as they are visited.

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

/* Connect two edges */
void edge_connect(edge *edges, unsigned int first, unsigned int second,
unsigned int *pos)
{
edges[*pos].first = first;
edges[*pos].second = second;
(*pos)++;
}

void print(unsigned int vertex)
{
printf("Visiting vertex %u\n", vertex);
}

int main(void)
{
const unsigned int size = 12; /* Edges */
const unsigned int order = 13; /* Vertices */
edge *edges = malloc(size * sizeof(edge));
unsigned int i = 0;
edge_connect(edges, 0, 1, &i);
edge_connect(edges, 0, 2, &i);
edge_connect(edges, 0, 3, &i);
edge_connect(edges, 0, 4, &i);
edge_connect(edges, 1, 5, &i);
edge_connect(edges, 1, 6, &i);
edge_connect(edges, 2, 7, &i);
edge_connect(edges, 2, 8, &i);
edge_connect(edges, 3, 9, &i);
edge_connect(edges, 3, 10, &i);
edge_connect(edges, 4, 11, &i);
edge_connect(edges, 4, 12, &i);

free(edges);
return 0;
}


The output:

Visiting vertex 0
Visiting vertex 1
Visiting vertex 2
Visiting vertex 3
Visiting vertex 4
Visiting vertex 5
Visiting vertex 6
Visiting vertex 7
Visiting vertex 8
Visiting vertex 9
Visiting vertex 10
Visiting vertex 11
Visiting vertex 12