DFS Graph Traversal для печати всех возможных путей, не пропуская ни одного участвующего края - PullRequest
0 голосов
/ 01 декабря 2019

Я хочу пройти по графику, чтобы извлечь все возможные пути от узла к другому. Я обнаружил, что в DFS могут отсутствовать некоторые пути, которые я хочу сохранить. Например, на графике я хочу пройти путь от узла 1 к узлу 5. Кажется, что DFS получает только 1-> 2 -> 3 -> 5, не получая 1-> 2 -> 3 -> 4-> 2 -> 3 -> 5. Поскольку при посещении узла 4 его узел-преемник 2 уже посещен. Тем не менее, я также хочу второй путь, так как я забочусь о каждом возможном участвующем ребре, например 3 -> 4 и 4 -> 2.

В настоящее время я просто сохранил множество неполных путей, таких как 1-> 2 -> 3-> 4 без следующей части до места назначения. Чтобы завершить их, я попытался найти узел 2 и объединить его с путями, начинающимися с узла 2. Я не уверен, является ли это правильным решением. Кажется, до сих пор не хватает некоторых возможностей. Есть ли какой-либо стандартный алгоритм, служащий для этой цели?
enter image description here

...