Introduction
Урок 1 из 9 курса Поиск в ширину — Алгоритмы на графах на Coddy.
С возвращением в серию Алгоритмы на графах! После поиска в глубину мы переходим к поиску в ширину (BFS) — второму фундаментальному способу обхода графа.
Там, где DFS погружается вглубь, BFS исследует граф слоями: сначала начальную вершину, затем всех её соседей, затем всё, что находится в двух шагах, и так далее. Именно этот послойный порядок позволяет BFS находить кратчайшие пути в невзвешенных графах.
Как и в остальной части серии, граф задается числом n (количество вершин, от 0 до n - 1) и edges — плоским массивом неориентированных пар [u0, v0, u1, v1, ...].
Давайте начнем!
Попробуйте сами
В этом уроке нет задания по программированию.
Проверьте себяВ этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.
