Implementation (Part 2)
Урок 6 из 9 курса Поиск в ширину — Алгоритмы на графах на Coddy.
Теперь мы обходим граф по слоям с помощью очереди.
Задание
СреднеТеперь создайте полный обход.
Напишите функцию с именем bfs, которая принимает n, плоский массив edges (неориентированный) и начальную вершину start, и возвращает порядок, в котором BFS посещает вершины, начиная с start.
Постройте список смежности (соседи отсортированы по возрастанию), затем используйте очередь: отметьте и добавьте в очередь начальную вершину, а затем многократно извлекайте вершину из очереди, записывайте её и добавляйте в очередь её непосещенных соседей. Посещаются только те вершины, которые достижимы из start.
Попробуйте сами
#include <stdlib.h>
int* bfs(int n, int* edges, int edges_size, int start, int* returnSize) {
// Напишите код здесь
*returnSize = 0;
return edges;
}
Проверьте себяВ этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.
Все уроки раздела Поиск в ширину — Алгоритмы на графах
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity