smihael smihael - 8 days ago 7
Java Question

Depth first search list paths to all end nodes

Hi I have a tree in which I would like to get paths from the initial (root) node to all leaves.

I found several algortithms that list (all) apths betwenn any given two nodes within a graph (for example this SO question:
Graph Algorithm To Find All Connections Between Two Arbitrary Vertices)

For binary tree there also exists an algorithm
http://techieme.in/print-all-paths-in-a-tree/
but I work on a tree with various branching factors.

Is there any better way of achieving what I want to do than traversing the tree once in order to get all leaves and then run the algorithm above for all leaves combined with the initial node?

I was thinking about implementing simple DFS extended by some additional stack containing all nodes alongt he path to a single leaf and then listing all sentences by looping through these stacks.

ArrayList<GrammarNode> discovered = new ArrayList<GrammarNode>();
Stack<GrammarNode> S = new Stack<GrammarNode>();


while (!S.empty()) {
node = S.pop();
if (!discovered.contains(node)) {
discovered.add(node);
System.out.println(node.getWord.getSpelling().trim());
for (GrammarArc arc : node.getSuccessors()) {
S.push(arc.getGrammarNode());
}
}
}


UPDATE:
The problem of this is that one has alyways go back to the root in order to generate full sentences. So I guess the question is: How to remember the node which was already fully visited (this means where all children nodes were already explored)?

Answer

Printing all paths from the root to every leaf would mean to print the entire tree so I'd just use a simple DFS and do the following for each node:

  • add it to the list/stack
  • if the node has children, repeat for the children
  • if the node is a leaf, print the list/stack
  • pop the node from the list/stack

Example:

   A
  / \
 B   E
/ \ / \
C D F G

The first steps would look like this:

  • put A on the list -> {A}
  • put B on the list -> {A,B}
  • put C on the list -> {A,B,C}
  • since C is a leaf, print the list (A,B,C)
  • remove C from the list -> {A,B}
  • put D on the list -> {A,B,D}
  • since D is a leaf, print the list (A,B,D)
  • ...
Comments