Как найти все пути (исключая циклы) от точки до точки на ориентированном графе?

Question

[x32net]

Есть ориентированный граф с циклами, состоит примерно из 1000 узлов.

Например для 1-4 будут пути: 1-5-4, 1-2-5-4.
Оптимальным подходом полагаю будет использовать представление графа и результатов в виде списков смежности.

Comments

[vaut]

А что с циклами делать?
В вашем примере из 4 в 3 есть бесконечное количество путей.

[x32net]

vaut: 4->3: 4-5-3, 4-1-5-3, 4-1-2-5-3. Получается 3 уникальных пути.

[vaut]

x32net: 4-1-5-2-1-

[x32net]

vaut: без повторов узла в цепи, в 4-1-5-2-1- повторяется 1 два раза.

[vaut]

x32net: это и было вопросом. Так как можно было повтор вершин разрешить, но запретить повтор ребер.

[x32net]

vaut: получается, надо запретить только повтор вершин?

Answer 1

[Сергей]

Ну очевидно тут нужно полным рекурсивным перебором находить.
Из точки А в точку Б пути идут разными способами, в том числе следующая после А будет точка С.
Т.о. чтобы найти все пути из точки А в Б, нужно найти все пути из С в Б + все пути из других точек смежных с А.
Применяя данное правило рекурсивно, можно обойти все вершины.

Answer 2

[x32net]

Сделал вариант решения https://play.golang.org/p/DjS_Umejsr
Как избавиться от повторов и убрать рекурсию?

Answer 3

[evgeniy_lm]

построить дерево

Comments

[Yrp]

посадить сына

[Анна]

вырастить дом