Generazione BFS foresta di grafici

Question

voglio generare una foresta BFS di di un DAG (Diretto aciclici Graph). Questo significa che i miei bisogni classe Tree di essere un albero generale e non un albero binario (in altre parole, non posso conoscere il numero di figli di un nodo avrà prima del tempo quando sto generando una foresta). La maggior parte del codice è scritto e mostrato sotto, però mi manca una linea che, per la vita di me, mi sfugge!

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;
}

negozi di classe il mio albero di un parametro di valore, un genitore di riferimento, e un elenco dei bambini. Il mio problema fa riferimento al nodo della struttura successiva. Una volta che ho aggiunto tutti i vicini di casa non visitati come bambino del nodo corrente, come faccio a portare al nodo successivo?

EDIT:

Quindi sarebbe simile a questa?

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));
        }   
    }
}

dove nasce il via chiamata ricorsiva?

Answer 1

Se ho capito bene la tua domanda, è possibile utilizzare la ricorsione per questo. In pratica si dispone di una funzione che crea uno strato di nodi poi si chiama di nuovo per ogni bambino che si desidera creare / visita.

Modifica:

Ok, ho modificato il codice un po '. Prima di tutto rimosso il caso (hasNext) come ridondante con il ciclo mentre all'interno di esso. Per ogni nodo bambino su vostri vicini elencare si crea un nuovo nodo della struttura allora esegue i suoi BFS metodo (), passando l'oggetto Albero attuale. La funzione restituisce una lista, che dovrebbe essere il percorso migliore attraverso l'albero. Io non sono anche sicuro circa il modo in cui si stanno ottenendo i nodi vicini, sembra un po 'strano. I havent provato il codice sia così ce n'è probabilmente errori di battitura e roba in esso, ma si spera che dovrebbe dare un'idea di come si può fare per la ricerca. Oh, e quando si colpisce un nodo foglia (il vostro target?), Si dovrà semplicemente impostare il suo peso e restituire una nuova lista con solo se stessa in esso.

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;   
}

Modifica 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);
        }
    }
}