Найти все пути на неориентированном графике

Question

У меня есть неориентированный граф, и я хочу перечислить все возможные пути от начального узла.Каждое соединение между 2 узлами уникально, в указанном пути уникально, например, представьте это графическое представление:

{A: [B, C, D],
 B: [A, C, D],
 C: [A, B, D],
 D: [A, B, C]}

некоторые перечисленные пути, начиная с A

A, B, C, D, A, C  in this path we have a connection between
A and B but we can't have a connection between B and A 

Я могу 'Это достигается с помощью существующего алгоритма, который я знаю, как DFS.Буду очень признателен за любую помощь.

Answer 1

Вероятно, наиболее интуитивным способом было бы, как ранее предлагалось, выполнять итерацию по всем соседям каждой потенциальной начальной точки, пока все пути не будут исчерпаны.

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

В псевдокоде это может дать что-то вроде этого:

paths = []
for node in graph
  visited = []
  path = [node]
  add node and path to stack-or-queue
  while node on stack-or-queue
    pop node and path
    for edges of node
      if edge is not visited
        add edge to visited
        add neighbour to path
        add neighbour and path to stack-or-queue
        add path to paths

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

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

Answer 2

Самый простой способ - это рекурсивно попробовать каждого соседа и объединить все результаты.

Это предполагает, что циклов нет - если вы разрешите циклы (как в вашем примере), будет бесконечно много путей.В этом случае вы можете создать генератор пути, ограничивая длину проверяемого пути, а затем перебирая все возможные длины пути.