Generating BFS forest of graphs

Question

I want to generate a BFS forest of of a DAG (Direct Acyclic Graph). This means my Tree class needs to be a general tree and not a binary tree (in other words, I can't know the number of children a node will have ahead of time when I am generating a forest). Most of the code is written and shown below, however I lack one line that, for the life of me, escapes me!

public Tree BFS(V start)
{
    reset();
    LinkedList<GraphMatrixVertex<V>> list = new LinkedList<GraphMatrixVertex<V>>();
    GraphMatrixVertex<V> vert = dict.get(start);
    Tree root = new Tree(vert); 
    list.add(vert);
    do
    {
        vert = list.getFirst();
        Iterator<V> ni = neighbors(start);
        while(ni.hasNext())
        {
            V v = ni.next();
            GraphMatrixVertex<V> vtx = dict.get(v);
            if(!vtx.isVisited())
            {
                list.add(vtx);
                            vtx.visit();
                root.addChild(new Tree(vtx));
            }
        }
    //code goes here
    }
    while(!list.isEmpty());

    return root;
}

My Tree class stores a value parameter, a parent reference, and a list of children. My problem is referencing the next tree node. Once I have added all the unvisited neighbors as childs of the current node, how do I get to the next node?

EDIT:

So it would look something like this?

public void bfs(Tree parent)
{   
    Iterator<V> ni = neighbors((V) parent.value());
    if(ni.hasNext())
    {
            while(ni.hasNext())
            {
            V next = ni.next();
            GraphMatrixVertex<V> vert = dict.get(next);
            if(!vert.isVisited())
                parent.addChild(new Tree(next));
        }   
    }
}

where does the recursive call go?

Answer 1

If I understand your question correctly, you can use recursion for this. Basically you have a function that creates a layer of nodes then calls itself again for each child you want to create/visit.

Edit:

Ok, I edited your code a little. First off I removed the if(hasNext) as its redundant with the while loop inside of it. For each child node on your neighbors list you create a new tree node then run its bfs() method, passing the current Tree object in. The function returns a list, which should be the best path through the tree. I'm also not sure about the way you are getting you neighboring nodes, it looks kinda odd. I havent tested the code either so theres probably typos and stuff in it, but hopefully it should give you an idea of how you can go about the search. Oh and when you hit a leaf node (your target?), it will need to just set its weight and return a new list with only itself in it.

int weight; // this should be you node traversal cost

public LinkedList<Tree> bfs(Tree parent){

    Iterator<V> ni = neighbors((V) parent.value());

    LinkedList bestPath = null;       
    int bestScore = 0xFFFFFFFF;

    while(ni.hasNext()){
        V next = ni.next();
        GraphMatrixVertex<V> vert = dict.get(next);
        if(!vert.isVisited()){
            Tree newNode = new Tree(next);
            parent.addChild(newNode);
            LinkedList path = newNode.bfs(this);
                if(newNode.weight < bestScore){
                    bestScore = weight;
                    bestPath = path;
                }
        }
    }
    weight = bestScore + this.weight;
    bestPath.addFirst(this);
    return path;   
}

Edit 2:

public void bfs(Tree parent){

    Iterator<V> ni = neighbors((V) parent.value());

    while(ni.hasNext()){
        V next = ni.next();
        GraphMatrixVertex<V> vert = dict.get(next);
        if(!vert.isVisited()){
            Tree newNode = new Tree(next);
            parent.addChild(newNode);
            newNode.bfs(this);
        }
    }
}