Поиск по первому дыханию (BFS) — это алгоритм, используемый для обхода дерева на графах или древовидных структурах данных. BFS можно легко реализовать с использованием рекурсии и структур данных, таких как словари и списки.
Алгоритм
- Выберите любой узел, посетите соседнюю непосещенную вершину, отметьте его как посещенное, отобразите и вставьте в очередь.
- Если не осталось соседних вершин, удалите первую вершину из очереди.
- Повторяйте шаги 1 и 2, пока очередь не станет пустой или не будет найден нужный узел.
Реализация
Рассмотрим график, который реализован в коде ниже:
graph = {'A' : ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': ['F' ], 'F': []} loaded = [] # Список для отслеживания посещенных узлов .queue = [] # Инициализация queuedef bfs (посещено, граф, узел): visit.append (узел) queue.append (узел) while queue: s = queue.pop (0) print (s, end = "") для соседа в графе [s]: если сосед не в посещенном: посещенный .append (сосед) queue.append (сосед) # Код драйвера bfs (посещенный, граф, 'A')
Пояснение
-
Строки 3-10 : иллюстрированный график представлен с помощью списка смежности . Простой способ сделать это в Python — использовать структуру данных словаря , где каждая вершина имеет сохраненный список своих смежных узлов.
-
Строка 12 :
посещено— это список, который используется для отслеживания посещенных узлов. -
Строка 13 :
queue— это список, который используется для отслеживания узлов, находящихся в настоящее время в очереди. -
Строка 29 : аргументы функции
bfs— это посещенныйграфв виде словаря и начальный узелA. -
Строки 15-26 :
bfsследует алгоритму, описанному выше:- Он проверяет и добавляет начальный узел в список
посещенныхи вочередь.. - Затем, пока очередь содержит элементы, она продолжает извлекать узлы из очереди, добавляет соседей этого узла в очередь, если они не посещены, и отмечает их как посещенные.
- Это продолжается до тех пор, пока очередь не станет пустой.
- Он проверяет и добавляет начальный узел в список
Сложность времени
Поскольку все посещаются узлы и вершины, временная сложность для BFS на графе составляет O ( V+E) O (V + E) O (V + E); где VV V — это количество вершин и EE E — количество ребер.
