Как реализовать поиск в ширину нерекурсивно для ориентированного графа на python

Question

Я пытаюсь реализовать функцию BFS, которая будет печатать список узлов ориентированного графа как посещенных с использованием обхода Breadth-First-Search. Функция должна быть реализована не рекурсивно, и она должна проходить через все узлы графа, поэтому при наличии нескольких деревьев она будет печататься следующим образом:

Дерево 1: а, б

Дерево 2: д, е, ч

Дерево 3: .....

Моя основная трудность заключается в понимании того, как заставить функцию BFS проходить через все узлы, если в графе есть несколько деревьев, без перепечатывания ранее посещенных узлов.

Answer 1

Для простоты вы можете использовать Очередь для выполнения BFS не рекурсивно.Здесь необходимы две структуры данных.

1. Очередь для поддержания порядка BFS.
2. Хэш-таблица элементов списка (или набор) для поиска дубликатов.

Это алгоритм:

1. Вставить начальную точку на графике в очередь, а также в хэш-таблицу.
2. Если очередь не пуста
   1. Исключение из очереди.
   2. Поставьте в очередь всех соседей исключенного элемента в очередь и вставьте их в набор, если их еще нет в наборе.
   3. Печать (/ access / process)элемент без очереди.
3. Повторяйте шаги со 2 по 4, пока очередь не будет исчерпана.

В сети можно найти множество примеров и оптимизаций.Например:

https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/

https://en.wikipedia.org/wiki/Breadth-first_search

Answer 2

BFS обычно выполняется с очередью.Когда вы обрабатываете узел, вы помещаете его потомков в очередь.После обработки узла вы обрабатываете следующий в очереди.

По своей природе это нерекурсивно.