パスをDFS形式でグラフに印刷する方法は？

Question

私はルートノードからすべての葉にパスを取得したいツリー（バイナリツリーではありません）を持っています。 たとえば、

A 
/| \ 
B C D 
/\ |/\ 
E F G H I 

私はすべてのパス= {A、B、E]を取得したい、[A、B、F]、[A、C、G]、[A、D、H]、 [私は今までやっていること、D、I]}

。

私はGraphクラスを持っています。

public class Graph { 
    static class Node{ 
     String name; 
     HashSet<Edge> inEdges; 
     HashSet<Edge> outEdges;} 
    static class Edge{ 
     Node from; 
     Node to; 
     String id;} 
}  

そして、このスニペットでツリーをトラバースします。

void printAllPaths(rootNode, list) { 
    System.out.println(rootNode.name); 
    list.add(rootNode.name); 
    int childCount = rootNode.outEdges.size(); 
    if (childCount == 0) { 
     System.out.println(list); 
     list.pop();//one for node 
     list.pop();//one for edge 
    } else { 
     for (Graph.Edge e : rootNode.outEdges) { 
      System.out.println(e.id); 
      list.add(e.id); 
      printAllPaths(e.to, list, rootNodeReplica); 
     } 
    } 
} 

基本的には何ですか。ノードに子がある場合

• は/ノードが葉の場合は、リストを印刷/リストからノードをスタックし、ポップ
• 上記と同様の操作を行い、スタック
• へのノードとエッジを追加しますしかし

を積み重ねます。 アルゴリズムが終了すると、Bノードが分岐してCに移動します。リストには{A Edge B}が残っていますが、ブランチを変更するときはノードAだけを含める必要があります。 AエッジBエッジCエッジGないエッジCエッジG。

どうすればこの問題を解決できますか？ ありがとうございます 親切にしてください

Answer 1

より簡単なバージョンの問題を見てみましょう。さあ、我々はチェーンA -- B -- Eを与えられて与えられている。次の三角形を印刷しました。

A 
A B 
A B C 
A B C 
A B 
A 

再帰を使用してもかまいませんか？もちろんできるよ！

void printEachPath(currentRoot, stack) { 
    if (currentRoot == null) return; 

    stack.push(currentRoot.name); 
    print stack; 

    printEachPath(currentRoot->next, stack); 

    print stack; 
    stack.pop(currentRoot.name); 
} 

私はあなたがこれからいくつかのヒントを得たことを願っています。