Trouver tous les chemins possibles dans le graphique

Question

Je cherche un algorithme qui m'aidera à trouver tous les chemins possibles dans un graphique. Tout ce que j'ai trouvé jusqu'à présent n'est pas entièrement satisfaisant.

Imaginons que nous avons un graphique (arbre) comme celui-ci:

Et nous allons utiliser un algorithme comme en largeur Recherche ou Profondeur Première recherche. En retour, nous allons obtenir quelque chose comme

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

Quelle est la façon dont nous traversons cet arbre et ce n'est pas ce que je cherche. J'aimerais obtenir tous chemins, comme:

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 

La chose est que je veux juste préciser noeud root et algorithme devrait être en mesure de me fournir tous les chemins possibles de toute longueur.

---

Jusqu'à présent, le code simple je ressemble:

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

Vous pouvez utiliser cet algorithme sur un arbre binaire pour imprimer tous ses chemins racine à feuilles. La fonction treePaths parcourt les nœuds en profondeur (DFS), en pré-commande, récursivement.

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

Juste fois le résultat et compte les nouvelles possibilités: Résultat = 9 (vous forgott le chemin [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