二维数组的广度优先搜索

Question

我有一个连接路径的网格，如下所示：

网格是按如下方式创建的二维数组：

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

根据给出的评论，这是答案的代码：

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

Answer 2

查看你的代码后，我发现错误是当你检查当前区块的邻居时，你只朝一个方向前进，直到你在那个方向有一个邻居，这样做你错过了一些邻居在队列中，当您通过最外层循环到达它们时，它们被视为新连接的组件，并且您的计数器会针对同一组件再次递增。

我对这个错误的解决方案是将 "else if" 更改为 "if" 即，如果任何块连接到当前块，则将其放入队列中。

希望对您有所帮助。

二维数组的广度优先搜索

Breadth-first-search on 2D array

javascript

algorithm

breadth-first-search

undirected-graph