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:

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

- If the neighbour is not in the visited set:

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); breadth_first_search(edges, size, order, print); 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