Поиск всех возможных путей в графике

Question

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

Давайте представим, что мы имеем граф (дерево), как этот:

И давайте используем некоторый алгоритм, как поиск в ширину или поиск в глубину. В ответ мы получим что-то вроде

1, 2, 4, (2), 5, (2), 6, (2), (1), 3, 7, 8, (7), 9 

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

1 
1, 2 
1, 2, 4 
1, 2, 5 
1, 2, 6 
1, 3 
1, 3, 7 
1, 3, 7, 8 
1, 3, 7, 9 

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

---

До сих пор, простой код у меня выглядит следующим образом:

func dfs(_ graph: Graph, source: Node) -> [String] { 
    var nodesExplored = [source.label] 
    source.visited = true 

    for edge in source.neighbors { 
     if !edge.neighbor.visited { 
      nodesExplored += dfs(graph, source: edge.neighbor) 
     } 
    } 

    return nodesExplored 
} 

Answer 1

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

treePaths(root, path[1000], 0) // initial call, 1000 is a path length limit 

// treePaths traverses nodes of tree DFS, pre-order, recursively 
treePaths(node, path[], pathLen) 
    1) If node is not NULL then 
     a) push data to path array: 
      path[pathLen] = node->data. 
     b) increment pathLen 
      pathLen++ 
    2) If node is a leaf node, then print the path array, from 0 to pathLen-1 
    3) Else 
     a) Call treePaths for left subtree 
      treePaths(node->left, path, pathLen) 
     b) Call treePaths for right subtree. 
      treePaths(node->right, path, pathLen) 

Answer 2

Просто сложите результат и рассчитывать новые возможности: Результат = 9 (вы forgott путь [1])

n0 n1 n2 n3 
1, 2, 4,  +3 
    (2), 5,  +1 
    (2), 6,  +1 
    (2),   +0 
(1), 3, 7, 8, +3 
     (7), 9 +1