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

Question

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

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

0 1 2 3 4 5 6 7 8 9

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

2-7-9

2-4-6-8-9

2-4-6-9

Для узла-1 моей следующей возможностью будет только узел-2, поэтому я не буду пробовать узел 0 и узел -3. Из-за некоторых специальных правил, которые я установил, только узел-2 подходит для узла-1. Следующие узлы для узла-2, узла-4 и узла-7 выбраны. Для узла-4 подходит только узел-6. Для узла 6 подходят узел 8 и узел 9. С другой стороны, для узла 7 следующим узлом будет только 9.

Все эти пути создаются и сохраняются в хэш-карте или в структуре списка.

DFS находит пути, например, между 0-1 и 1-3, которые для меня неприемлемы. Поскольку характер алгоритма, он находит кратчайший путь. Я хочу, чтобы все возможности по правилу были не самыми короткими. Правило не проблема, поэтому я не хочу, чтобы вы смущались и скучали. Для меня важен общий способ решения этой проблемы.

Заранее спасибо

Answer 1

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

Простейшим является определение класса для представления узла. В классе есть список массивов всех «дочерних» узлов этого «родителя». Также в узле есть целое число, которое используется в качестве «курсора» для вашего первого шага по глубине. (Не мешает также иметь другую целочисленную / символьную строку, которая является # узлом или другим идентификатором.)

Установить целое число "курсор" во всех узлах на ноль. Выберите свой начальный узел - сделайте его «текущим узлом». Вызовите метод на этом узле, чтобы пройти его. Он поднимает курсор и извлекает соответствующий элемент списка массива. Затем он вызывает метод walk для узла в этом элементе списка массивов. По возвращении «курсор» увеличивается.

Метод walk возвращается, когда достигает целевого узла или когда курсор увеличивается на размер, превышающий размер дочернего массива.

По пути вы ведете любую запись пути, который хотите. Одним из способов является передача списка массивов узлов, посещаемых при каждом вызове «walk», добавление текущего узла в список перед его передачей. Когда прогулка доходит до конечного узла, список массивов копируется как один из ответов. По возвращении из «прогулки» добавленный элемент удаляется.

Answer 2

Вы захотите использовать поиск в ширину , используя Очередь .

Редактировать: после повторного чтения вашего вопроса, я думаюпроблема заключается в том, как вы представляете направленный граф, а не в том, какой алгоритм вы выберете.Либо DFS, либо BFS подойдут для вашего случая, но вам нужно правильно реализовать график, чтобы алгоритм знал, что путь не должен идти в неправильном направлении.

DFS находит пути, например, между0-1 и 1-3 которые для меня неприемлемы.Поскольку характер алгоритма, он находит кратчайший путь.Я хочу, чтобы все возможности по правилу, а не самые короткие.

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