javascript - 二维数组的广度优先搜索

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

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

我对这个错误的解决方案是将“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);
}