如何在图中以DFS方式打印路径？

-1

我有一棵树（不是二叉树），其中我想从根节点到所有树叶的路径。例如， ;如何在图中以DFS方式打印路径？

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

我想获得的所有路径= {[A，B，E]，[A，B，F]，[A，C，G]，[A，d，H]， [ A，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。

我该如何解决这个问题？在此先感谢亲切的问候

来源

2016-11-06 yns

除了当从列表中删除节点时，您已经明白了。当你离开一个节点时（即你已经遍历节点及其所有后继节点），你不希望它在任何路径上出现。 – halfo

谢谢@halfo。但我无法完全理解。你能举个例子吗？ – yns

让我们看看更简单的版本的问题。说，我们给了一个链条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); 
}

我希望你能从中得到一些提示。

来源

2016-11-07 09:19:14 halfo

如何在图中以DFS方式打印路径？

回答

相关问题