Для алгоритма нам потребуются очередь и множество посещенных вершин was, которые изначально содержат одну вершину s. На каждом шаге алгоритм берет из начала очереди вершину v и добавляет все непосещенные смежные с v вершины в was и в конец очереди. Если очередь пуста, то алгоритм завершает работу.
//псевдокод
create a queue Q
mark v as visited and put v into Q
while Q is non-empty
remove the head u of Q
mark and enqueue all (unvisited) neighbours of u
/*си*/
// BFS algorithm
void bfs(struct Graph* graph, int startVertex) {
struct queue* q = createQueue();
graph->visited[startVertex] = 1;
enqueue(q, startVertex);
while (!isEmpty(q)) {
printQueue(q);
int currentVertex = dequeue(q);
printf("Visited %d\\n", currentVertex);
struct node* temp = graph->adjLists[currentVertex];
while (temp) {
int adjVertex = temp->vertex;
if (graph->visited[adjVertex] == 0) {
graph->visited[adjVertex] = 1;
enqueue(q, adjVertex);
}
temp = temp->next;
}
}
}