Генерация леса графов BFS

Question

Я хочу создать лес BFS из DAG (прямой ациклический граф).Это означает, что мой класс Tree должен быть общим деревом, а не бинарным деревом (другими словами, я не могу знать, сколько дочерних узлов будет иметь узел раньше времени, когда я создаю лес).Большая часть кода написана и показана ниже, однако мне не хватает одной строки, которая, на всю жизнь, ускользает от меня!

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 хранит параметр значения, родительскую ссылку и списокдетей.Моя проблема связана со ссылкой на следующий узел дерева.После того, как я добавил всех не посещенных соседей в качестве дочерних элементов текущего узла, как мне перейти к следующему узлу?

РЕДАКТИРОВАТЬ:

Так что бы это выглядело примерно так?

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

куда идет рекурсивный вызов?

Answer 1

Если я правильно понимаю ваш вопрос, вы можете использовать для этого рекурсию. По сути, у вас есть функция, которая создает слой узлов, а затем снова вызывает себя для каждого дочернего элемента, которого вы хотите создать / посетить.

Edit:

Хорошо, я немного отредактировал твой код. Прежде всего, я удалил if (hasNext) как его избыточность с циклом while внутри него. Для каждого дочернего узла в вашем списке соседей вы создаете новый узел дерева, затем запускаете его метод bfs (), передавая текущий объект Tree. Функция возвращает список, который должен быть наилучшим путем через дерево. Я также не уверен в том, как вы получаете соседние узлы, это выглядит странно. Я тоже не тестировал код, так что, возможно, в нем есть опечатки и прочее, но, надеюсь, он должен дать вам представление о том, как вы можете проводить поиск. Да, и когда вы нажмете на листовой узел (ваша цель?), Ему нужно будет просто установить его вес и вернуть новый список, содержащий только себя.

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

Редактировать 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);
        }
    }
}