• Обработка вершин графа по мере удаления от стартовой вершины
• Компьютерное моделирование, графические интерфейсы, анализ пропускной способности транспортных, электрических и т.п. цепей и сетей, …
• Алгоритмы обработки графов Поиск кратчайших путей Вычисление максимального потока Проверка связности

Для алгоритма нам потребуются очередь и множество посещенных вершин 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;
    }
  }
}

Сложность: