0

DAG（Direct Acyclic Graph）のBFSフォレストを生成したい。つまり、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));
        }   
    }
}

再帰呼び出しはどこに行きますか？

4

1 に答える 1

1

私があなたの質問を正しく理解しているなら、あなたはこれに再帰を使うことができます。基本的に、ノードのレイヤーを作成し、作成/訪問する子ごとにそれ自体を再度呼び出す関数があります。

編集：

わかりました。コードを少し編集しました。最初に、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);
        }
    }
}
于 2010-08-18T08:23:25.137 に答える