javascript - 2D 配列の幅優先探索

Question

以下に示すように、接続されたパスのグリッドがあります。

グリッドは、次のように作成された 2D 配列です。

for(var x = 0; x < 10; x++){
        hz[x] = new Array(10);

        for(var y = 0; y < 10; y++){
            hz[x][y] = new block(0, 0, 0, 0, 0);
        }
    }

配列の各要素には、次のような型のオブジェクトが含まblockれます。

function block(top, bottom, left, right, visited){
    this.top = top;
    this.bottom = bottom;
    this.left = left;
    this.right = right;
    this.visited = visited;
}

接続されたコンポーネントを定義するために、グリッドに幅優先検索を実装しました。完全に接続する必要があります。これは、BFS の私のコードです。

function search(){
    var count = 0;
    var graph = hz;

    for(var x=0; x < 9; x++){
        for(var y=0; y < 9; y++){
            if(!graph[x][y].visited){ //if block not yet visited
                count++;
                q = new Queue();
                q.enqueue(graph[x][y]);
                graph[x][y].visited = 1;

                while(q.size() > 0){
                    var w = q.dequeue();
                    var ends = numberOfEnds(w);
                    var a = w.x;
                    var b = w.y;

                    for(var t=0; t < ends; t++){
                        if(w.left){
                            if(graph[a][b-1].right){
                                if(!graph[a][b-1].visited){
                                    graph[a][b].left = 0;
                                    graph[a][b-1].visited = 1;
                                    q.enqueue(graph[a][b-1]);
                                }
                            }
                        }
                        else if(w.right){
                            if(graph[a][b+1].left){
                                if(!graph[a][b+1].visited){
                                    graph[a][b].right = 0;
                                    graph[a][b+1].visited = 1;
                                    q.enqueue(graph[a][b+1]);
                                }
                            }
                        }
                        else if (w.top){
                            if(graph[a-1][b].bottom){
                                if(!graph[a-1][b].visited){
                                    graph[a][b].top = 0;
                                    graph[a-1][b].visited = 1;
                                    q.enqueue(graph[a-1][b]);
                                }
                            }
                        }
                        else if (w.bottom){
                            if(graph[a+1][b].top){
                                if(!graph[a+1][b].visited){
                                    graph[a][b].bottom = 0;
                                    graph[a+1][b].visited = 1;
                                    q.enqueue(graph[a+1][b]);
                                }
                            }
                        }
                    } //end for every neighbour of block
                } //end while

            } //end if visited
        } //end for y
    } //end for x

    console.log("Count: " + count);
}

問題は、アルゴリズムを実行すると、結果countが非​​常に高くなることです。50 年代のように、せいぜい 1 または 2 である必要があります。

私は何を間違っていますか？

Answer 1

あなたのコードを見た後、私が見つけた間違いは、現在のブロックの隣人をチェックしているときに、その方向に隣人がいるまで一方向にしか進んでいないことです。それらは新しい接続されたコンポーネントと見なされる最も外側のループによってそれらに到達し、同じコンポーネントに対してカウンターが再度インクリメントされます。

この間違いに対する私の解決策は、「else if」を「if」に変更することです。つまり、現在のブロックに接続されているブロックがある場合は、それをキューに入れます。

これがお役に立てば幸いです。

Answer 2

与えられたコメントに基づいて、これは答えのコードです：

function search(){
    var count = 0;
    var graph = hz;

    for(var x=0; x < 9; x++){
        for(var y=0; y < 9; y++){
            if(!graph[x][y].visited){ //if block not yet visited
                count++;
                console.log("Component: " + count);
                q = new Queue();
                q.enqueue(graph[x][y]);
                graph[x][y].visited = 1;

                while(q.size() > 0){
                    var w = q.dequeue();
                    var ends = numberOfEnds(w);
                    var a = w.x;
                    var b = w.y;


                        if(w.left){
                            if(graph[a][b-1].right){
                                if(!graph[a][b-1].visited){
                                    graph[a][b].left = 0;
                                    graph[a][b-1].visited = 1;
                                    q.enqueue(graph[a][b-1]);
                                }
                            }
                        }
                        if(w.right){
                            if(graph[a][b+1].left){
                                if(!graph[a][b+1].visited){
                                    graph[a][b].right = 0;
                                    graph[a][b+1].visited = 1;
                                    q.enqueue(graph[a][b+1]);
                                }
                            }
                        }
                        if (w.top){
                            if(graph[a-1][b].bottom){
                                if(!graph[a-1][b].visited){
                                    graph[a][b].top = 0;
                                    graph[a-1][b].visited = 1;
                                    q.enqueue(graph[a-1][b]);
                                }
                            }
                        }
                        if (w.bottom){
                            if(graph[a+1][b].top){
                                if(!graph[a+1][b].visited){
                                    graph[a][b].bottom = 0;
                                    graph[a+1][b].visited = 1;
                                    q.enqueue(graph[a+1][b]);
                                }
                            }
                        }

                } //end while

            } //end if visited
        } //end for y
    } //end for x

    console.log("Count: " + count);
}