Найти все обходы BFS/DFS

Учитывая неориентированный циклический граф, я хочу найти все возможные обходы с помощью поиска в ширину или поиска в глубину. Это дается граф в виде списка смежности:

A-BC
B-A
C-ADE
D-C
E-C

Таким образом, все пути BFS от корня A будут такими:

{ABCDE,ABCED,ACBDE,ACBED}

и для ДФС:

{ABCDE,ABCED,ACDEB,ACEDB}

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

Любая помощь будет оценена по достоинству.


graph traversal graph-traversal
person Madnebular    schedule 28.10.2012    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Помимо очевидного способа, когда вы фактически выполняете все возможные обходы DFS и BFS, вы можете попробовать этот подход:

Шаг 1. В обходе dfs, начиная с корня A, преобразуйте список смежности текущего посещаемого узла следующим образом: Сначала удалите родителя узла из списка. Во-вторых, сгенерируйте все перестановки оставшихся узлов в списке adj.

Итак, если вы находитесь в узле C, пришедшем из узла A, вы сделаете:

C -> ADE transform into C -> DE transform into C -> [DE, ED]

Шаг 2. После шага 1 у вас есть следующий преобразованный список adj:

A -> [CB, BC]
B -> []
C -> [DE, ED]
D -> []
E -> []

Теперь вы запускаете обработку, начиная с (A,0), где первый элемент в паре — это путь обхода, а второй — индекс. Предположим, у нас есть две очереди. Очередь BFS и очередь DFS. Ставим эту пару в обе очереди.

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

Мы выталкиваем первую пару из очереди. Получаем (А,0). Узел A отображается на [BC, CB]. Итак, мы генерируем два новых пути (ACB,1) и (ABC,1). Поместите эти новые пути в очередь.

Возьмите первый из них из очереди, чтобы получить (ACB,1). Индекс равен 1, поэтому мы смотрим на второй символ в строке пути. Это C. Узел C отображается на [DE, ED].

  • Дочерними элементами BFS этого пути будут (ACBDE,2) и (ACBED,2), которые мы получили путем добавления дочерней перестановки.
  • Дочерние DFS этого пути будут (ACDEB,2) и (ACEDB,2), которые мы получили, вставив дочернюю перестановку сразу после C в строку пути.

Мы генерируем новые пути в зависимости от того, с какой очередью мы работаем, на основе вышеизложенного и помещаем их в очередь. Поэтому, если мы работаем с очередью BFS, мы вставляем (ACBDE,2) и (ACBED,2). Содержимое нашей очереди теперь: (ABC,1), (ACBDE,2), (ACBED,2).

Мы вытаскиваем (ABC,1) из очереди. Сгенерируйте (ABC,2), так как B не имеет потомков. И получите очередь: (ACBDE,2), (ACBED,2), (ABC,2) и так далее. В какой-то момент мы получим кучу пар, где индекс не содержится в пути. Например, если мы получаем (ACBED,5), мы знаем, что это законченный путь.

person cyon    schedule 28.10.2012
comment
Я рассматривал это и для DFS, но что произойдет, если у узла есть несколько потенциальных родителей? ОП утверждает, что график циклический (хотя в примере это не так). Предположим, между B и D было добавлено ребро, производит ли оно по-прежнему все обходы? Дочерние перестановки должны учитывать узлы, которые уже были посещены. - person Origin; 29.10.2012
comment
Да хороший момент. Я полагаю, что OP необходимо указать, помнят ли обходы посещенные узлы. Предполагая, что они это делают, и ему нужен конечный обход, я думаю, на каждом шаге, когда ваш индекс указывает на узел, вы можете проверить, содержится ли эта буква в подстроке до индекса. Если это вы удалите это письмо и попробуйте следующее письмо. Если это не так, вы добавляете дочерние перестановки. - person cyon; 29.10.2012

arrow_upward
0
arrow_downward

BFS должен быть достаточно простым: у каждого узла есть определенная глубина, на которой он будет найден. В вашем примере вы найдете A на глубине 0, B и C на глубине 1, а E и D на глубине 2. В каждом пути BFS у вас будет элемент с глубиной 0 (A) в качестве первого элемента, за которым следует любая перестановка элементы на глубине 1 (B и C), за которыми следует любая перестановка элементов на глубине 2 (E и D) и т. д. Если вы посмотрите на свой пример, ваши 4 пути BFS соответствуют этому шаблону. A всегда является первым элементом, за которым следует BC или CB, а затем DE или ED. Вы можете обобщить это для графов с узлами на большей глубине. Чтобы найти это, все, что вам нужно, это 1 поиск Дейкстры, что довольно дешево.

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

person Origin    schedule 28.10.2012