Реализуйте алгоритм поиска в ширину (BFS - Breadth-First Search) для графа на Python. Напишите код и объясните, как работает этот алгоритм. Обсудите его сложность и применение.
Объяснение:
Алгоритм поиска в ширину (BFS) используется для обхода или поиска в графе. Он начинает с выбора стартовой вершины и пошагово распространяется по всем смежным вершинам.
Шаги алгоритма:
1. Создается пустое множество
visited для отслеживания посещенных вершин и очередь queue для управления порядком обхода.2. Стартовая вершина добавляется в очередь и отмечается как посещенная.
3. Пока очередь не пуста, извлекается вершина из начала очереди (
queue.popleft()).4. Выводится значение текущей вершины и добавляются в очередь все её смежные вершины, которые еще не были посещены.
5. Шаги 3-4 повторяются до тех пор, пока очередь не опустеет.
Сложность:
Временная сложность: O(V + E), где V — количество вершин, E — количество ребер в графе.
Пространственная сложность: O(V), так как используется множество для отслеживания посещенных вершин.
Применение:
BFS применяется в задачах поиска кратчайших путей в невзвешенных графах.
Он также используется в задачах, связанных с обходом графов, например, в нахождении компонент связности.