Как отследить путь, который посещает все узлы в bfs / dfs

Question

Это похоже на Как отследить путь в поиске по ширине? , но метод, описанный в ответах в этом посте, не работает для моего случая, кажется.

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

Рассмотрим неориентированный граф с вершинами V = {a, b, c} и ребрами = {{a, b}, {a, c}} и предположим, что мы должны пройти по наследникам в алфавитном порядке. Мы начинаем с узла a, и конечным состоянием является посещение всех 3 узлов.

При поиске по ширине сначала будет проходить ребро a->b, а затем ребро a->c. Таким образом, путь решения a->b->a->c. Поскольку между b & c нет ребра, мы должны go вернуться назад через a (поэтому мы должны пройти через край b->a). В ответе в вышеупомянутом связанном сообщении принятое решение только вывело бы a->c.

Я не могу придумать, как изменить обычный алгоритм BFS для этого. У меня тот же вопрос к dfs, но сейчас я бы хотел начать с bfs.

Answer 1

Кажется странным хотеть сделать это. Это, конечно, проще с поиском по глубине (DFS), который всегда следует либо за ребром, либо возвращается назад по этому ребру. Напротив, поиск в ширину (BFS), как правило, не посещает (или не отслеживает) узел, соседний с предыдущим посещенным.

В частности, эта часть вашего вопроса неверна и выдает ошибочное представление:

Поскольку между b & c нет ребра, мы должны go вернуться назад через a (поэтому мы должны пересечь ребро b -> a).

BFS никогда не будет пересекать край обратно от b до a в вашем примере. Он завершает посещение b, затем опрашивает c из очереди и сразу посещает c, не «путешествуя» туда через a.

Для аналогии имеет смысл думать о DFS как отслеживание пути; если вы находитесь в лабиринте, вы можете использовать крошки, чтобы пометить места, которые вы "посетили", и, следовательно, решить лабиринт с помощью DFS. Напротив, человек не может решить лабиринт с помощью BFS, потому что у людей не может быть очереди мест, к которым он знает, как добраться, и «телепортироваться» к следующему месту в очереди. BFS осмысленно не отслеживает путь, по которому вы могли бы идти, путешествуя по краям графа.

---

При этом, если вы действительно хотите, вы можете построить путь, посещая узлы графа, так что каждый узел посещается в первый раз в том же порядке, что и BFS. Самый простой способ сделать это - создать BFS для построения списка узлов в «порядке BFS», а также построить «дерево BFS». Затем для каждого узла в порядке BFS вы можете получить к нему информацию от предыдущего узла, пройдя через своего наименьшего общего предка в дереве BFS. Этот путь проходит только через узлы, которые уже были посещены ранее в порядке BFS.