0

リンクされたリストの配列として構築されている隣接行列のbfsの実行に取り組んでいます。

これが私のbfsメソッドで、リンクされたリストと開始位置の配列を受け取ります:

public static int bfs(List<Integer>[] smallWorld, int start){


    int distance = 0;
    int size = smallWorld.length;

    //for each location in smallWorld do a bfs to every other location      
    int u;
    int white = 0, grey = 1, black = 2;
    int [] color, d, pie;
    Queue <Integer> q = new <Integer> LinkedList();

    color = new int [size];
    d = new int [size];
    pie = new int [size];

    for( int x = 0; x < size; x++){
        color[x] = white;
        d[x] = -1;
        pie[x] = -1;
    }

    color[start] = grey;
    d[start] = 0;
    pie[start] = -1;
    q.addAll(smallWorld[start]);        //enqueue the adjacent items
    while(!q.isEmpty()){
        u = q.remove();
        for(int v = 0; v < smallWorld[u].size(); v++){      //for every vertex u is adjacent to
            if(color[v] == white){
                color[v] = grey;
                d[v] = d[u] + 1;
                pie[v] = u;
                q.addAll(smallWorld[v]);
            }
        }
        color[u] = black;
    }

    int x = 0;
    while(d[x] != -1){
        distance = distance + d[x];
        x++;
    }

本当に smallWorld の長さは 500 ですが、テスト目的で、配列の最初のインデックスで bfs を実行しているだけです。（bfsは、配列内の2つのインデックス間の最短パスを返すことになっていることを知っています）。私は現在約14分間実行されていますが、理由はわかりません。つまり、!isEmpty()が原因だと思いますが、遅かれ早かれ白が不足しなければならない場合にのみキューに追加されます。

編集。無限ループの問題は解決したが、BFS メソッドはまだ 100% ではない

なぜそれが機能しないのですか？つまり、アルゴリズムに従って T を処理しましたが、アルゴリズムは通常、リンクされたリストの配列を参照していません。

この問題を解決するためのアイデア

4

1 に答える 1

4

問題は、この while ループにある可能性があります。xをインクリメントしていません。

int x = 0;
while(d[x] != -1){
    distance = distance + d[x];
}
于 2013-04-10T06:48:51.700 に答える