BFS
Урок 10 из 14 курса Графы — Серия «Структуры данных» №9 на Coddy.
Следующие задачи предназначены для использования класса Graph, который вы только что создали.
Каждая задача предоставляет вам заблокированный файл graph (финальный Graph из предыдущей главы) и новый файл solution, в котором вы напишете функцию, ИСПОЛЬЗУЮЩУЮ Graph.
Наш первый алгоритм: Breadth-First Search (поиск в ширину). Начиная с вершины, BFS посещает все достижимые вершины волнами: сначала начальную, затем все, что находится на расстоянии одного ребра, затем все, что на расстоянии двух ребер, и так далее. Классическая реализация использует queue (очередь): добавьте в очередь начальную вершину, затем многократно извлекайте из очереди, помечайте вершину как посещенную и добавляйте в очередь любых непосещенных соседей.
Поскольку списки соседей не имеют фиксированного порядка, два корректных запуска BFS могут привести к разным порядкам обхода. Чтобы сделать ответ детерминированным в этой задаче, отсортируйте соседей каждой вершины по возрастанию перед добавлением их в очередь.
Задание
ЛегкоНапишите функцию bfs, которая принимает двумерный массив целых чисел adjacency (где каждая строка представляет собой ребро [u, v]) и целое число start, и возвращает порядок обхода BFS, начиная с start, в виде списка целых чисел.
Постройте граф: для каждой пары [u, v] в adjacency вызовите g.addEdge(u, v). Затем выполните BFS от вершины start, используя очередь. При обработке соседей вершины сортируйте их по возрастанию, чтобы результат был детерминированным.
Вы должны использовать класс Graph (предоставленный в graph) — не используйте встроенные средства языка (карты, множества) для моделирования смежности. Вспомогательные данные для алгоритма (множества посещенных вершин, очереди) могут использовать типы из стандартной библиотеки.
Попробуйте сами
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start;
if (scanf("%d %d %d", &n, &m, &start) != 3) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
int out[MAX_VERTICES];
int outn = bfs(adjacency, m, start, out);
for (int i = 0; i < outn; i++) {
if (i > 0) printf(" ");
printf("%d", out[i]);
}
printf("\n");
return 0;
}