2

これは私のbfsアルゴリズムです。通過したエッジの数をフィールドエッジに保存したいのですが、変数を配置して各エッジに1つ追加する場所がわかりません。私は長すぎる答えを得続けているので、これは単にエッジを増やすよりも難しいと思います。

これは、余分なエッジではなく、実際のパスに沿ったエッジのみを計算することになっていることに注意してください。 

public int distance(Vertex x, Vertex y){
        Queue<Vertex> search = new LinkedList<Vertex>();
        search.add(x);
        x.visited = true;
        while(!search.isEmpty()){
            Vertex t = search.poll();
            if(t == y){
                return edges;
            }
            for(Vertex n: t.neighbours){
                if(!n.visited){
                    n.visited = true;
                    search.add(n);
                }

            }
            System.out.println(search + " " + t);
        }
        return edges;   
    }

ありとあらゆる助けをいただければ幸いです。より多くのクラス/メソッドが必要な場合は私に知らせてください

編集

import java.util.ArrayList;

public class Vertex {

    public static char currentID = 'a';
    protected ArrayList<Vertex> neighbours;
    protected char id;
    protected boolean visited = false;
    protected Vertex cameFrom = null;
    public Vertex(){
        neighbours = new ArrayList<Vertex>();
        id = currentID;
        currentID++;
        Graph.all.add(this);
    }
    public void addNeighbour(Vertex x){
        int a;
        while(x == this){
             a = (int) (Math.random()*(Graph.all.size()));
             x = Graph.all.get(a);
        }           
            if(!(neighbours.contains(x))){
                neighbours.add(x);
                x.addNeighbour(this);
                //System.out.println(this + " Linking to " + x);
            }
    }
    public void printNeighbours(){
        System.out.println("The neighbours of: " + id + " are: " + neighbours);
    }
    public String toString(){
        return id + "";
    }

}
4

2 に答える 2

2

Vertexクラスで、そのノードが訪問されたときに来たVertex cameFrom場所を指すように設定するフィールドを作成します。フィールドをこれVertexに置き換えることもできます(まだアクセスされていない場合) 。boolean visitednullVertex

次に、ポインターが見つかったらVertex y、ポインターをたどって、Vertex x移動中に必要なステップ数を数えます。

Vertexクラスを変更したくない場合はMap<Vertex,Vertex>、検索中に、アクセスしている頂点から元の頂点へのマッピングを保存するだけにしてください。最後までたどり着いたら、同じように最初への道をたどることができます。

おそらくこれらの線に沿った何か：

    public int distance(Vertex x, Vertex y){
        Queue<Vertex> search = new LinkedList<Vertex>();
        search.add(x);
        while(!search.isEmpty()){
            Vertex t = search.poll();
            if(t == y){
                return pathLength( t );
            }
            for(Vertex n: t.neighbours){
                if(n.cameFrom == null || n != x){
                    n.cameFrom = t;
                    search.add(n);
                }

            }
            System.out.println(search + " " + t);
        }
        return -1;  
    }

    public int pathLength( Vertex v )
    {
       int path = 0;

       while ( v.cameFrom != null )
       {
         v = v.cameFrom;
         path++;
       }

       return path;
    }
于 2012-04-08T04:06:55.120 に答える
1

この例では、エッジの数は単純に のサイズですsearch。列。

編集：

考えられる解決策の 1 つは、レイヤーごとに実行することです。頂点 A と F の間の距離を求めたとします。

グラフは次のようになります。

A
|\
B C
|
D
|\
E F

まず、A と B、C の間の距離を計算します (B と C は A のすぐ隣にあるため、これは簡単です。次に、A と D の間の距離を計算します (D は B のすぐ隣にあるため、簡単です。次に A と E、 F. 距離を A 頂点ノードに保存します. BFS を実行して検索結果を確認したら、距離を尋ねるだけです.このビジュアル ダイアグラムを見てください.

于 2012-04-08T03:47:29.940 に答える