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

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

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

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

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

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


search graph graph-traversal breadth-first-search depth-first-search
person 24n8    schedule 08.02.2020    source источник
comment
a->b->a->c представляет собой последовательность посещенных узлов. Путь - это не та последовательность. Путь от a к c проходит не через b, а напрямую через a>c.   -  person c0der    schedule 09.02.2020
comment
Но если вы проходите по преемникам в алфавитном порядке, путь к c из a должен будет пройти через b.   -  person 24n8    schedule 09.02.2020
comment
Верно. Вы идете в поисках пути. Последовательность перемещения действительно a->b->a->c . Найден путь a->c   -  person c0der    schedule 10.02.2020
comment
Пожалуйста, ответьте на два опубликованных ответа   -  person c0der    schedule 12.02.2020

Ответы (1)


arrow_upward
0
arrow_downward

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

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

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

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

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

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

person kaya3    schedule 10.02.2020
comment
На самом деле это была часть проекта, а именно задача коммивояжера, где перед нами стояла задача найти непрерывный путь через граф, который посещает все города, используя различные методы поиска, такие как BFS, DFS, UCS, A* и т. д. В конце концов я понял, как это сделать, и это нужно было сделать в пространстве состояний, а не в пространстве графа. - person 24n8; 11.02.2020