CODEWITHSUNDEEP
javagraph-algorithm
smihael
smihael

Reputation: 913

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)?

Upvotes: 4

Views: 8162

Answers (4)

nm15
nm15

Reputation: 1

A slight modification of DFS (which includes back-tracking) prints all the paths from a given source. In the below example the graph is represented in adjacency list format.

  public void mDFS(ArrayList<node> v,int ind,ArrayList<Boolean> visit,ArrayList<node> tillNow){
    visit.set(ind,true);
    node n = v.get(ind);
    int len = n.adj.size();
    tillNow.add(n);
    int count = 0;
    for(node tmp: n.adj){
      if( !visit.get(tmp.id) ){      
        count++;
        tmp.pre = ind;
        mDFS(v,tmp.id,visit,tillNow); // id gives index of node in v
      }
    }
    if(count == 0){
      for(node tmp: tillNow){
        System.out.print((tmp.id + 1) + " - ");
      }System.out.print("\n");
    }
    visit.set(ind,false);
    tillNow.remove(tillNow.size() - 1);
    return;
  }

Upvotes: 0

Yar
Yar

Reputation: 7476

So here's a sample approach. Note that you need an extra visited field in your node structure:

public class TreeNodeExtra {
    int val;
    TreeNodeExtra left;
    TreeNodeExtra right;
    boolean visited;
    TreeNodeExtra (int v) {
        val = v;
        visited = false;
    }
}

private ArrayList<ArrayList<TreeNodeExtra>> all_path_from_root_to_leaf(TreeNodeExtra root) {
    Stack<TreeNodeExtra> st = new Stack<>();
    ArrayList<ArrayList<TreeNodeExtra>> res = new ArrayList<>();
    st.push(root);
    root.visited = true;

    while (!st.isEmpty()) {
        TreeNodeExtra top = st.peek();
        if (top.left != null && !top.left.visited) {
            st.push(top.left);
            top.left.visited = true;
        }
        // if left node is null
        else {
            if (top.right == null && top.left == null) {
                // we have a leaf
                ArrayList<TreeNodeExtra> tmpList = new ArrayList<>();
                for (TreeNodeExtra t : st) {
                    tmpList.add(t);
                }
                res.add(tmpList);
                st.pop();
            }
            else if (top.right != null && !top.right.visited) {
                st.push(top.right);
                top.right.visited = true;
            }
            else {
                st.pop();
            }
        }
    }

    return res;
}

Upvotes: 0

Thomas
Thomas

Reputation: 88747

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)
  • ...

Upvotes: 3

Maurice Perry
Maurice Perry

Reputation: 32831

if you know that the graph is indeed a tree (there is only one path to each node), them yes, a simple DFS would be more efficient (at least from a memory usage point of view). Otherwise, you can also use the iterative deepening DFS.

Upvotes: 0

Related Questions