简谈BFS

BFS的最好理解就是“层次遍历”，他是一层层往下走的。时间复杂度同DFS。

重点在于使用队列来缓存要遍历的结点。

给出核心代码（c++）：使用STL中的queue,vex[v][v_i] is adjacent matrix

 queue<int> que;

 que.push(v0); //v0是起始点

 while(!que.empty()){

     int v = que.front(); //取队头

     que.pop(); //出队

     for(int vi=;vi<n;vi++){

         if(vex[v][vi]){

             que.push(vi); //vi入队

         }

     }

 }

BFS可以推广到三维数组，用于计算由像素块组成的三维不规则物体体积、三维物体的连通情况。之前在PAT题目中遇到过一次，在此特别记录一下这样题目的处理方法。

这种题目是二维BFS走迷宫过程的一种扩展。先说一下三维数组的表示以及初始化：

pixel vex[][][];

for(int z=;z<l;z++){

    for(int x=;x<n;x++){

       for(int y=;y<m;y++){

            vex[z][x][y].x = x;

            vex[z][x][y].y = y;

            vex[z][x][y].z = z;

            vex[z][x][y].state = ;

         }

     }

}

假设v[z][x][y]=1说明这点被像素所填充，这样上面的代码就构造了n*m*l完全被填充的立方体。

再来假设搜索位上下左右前后，那么BFS的方向数组又该如何设计？

 int x[] = {,,-,,,};

 int y[] = {,,,-,,};

 int z[] = {,,,,,-};

那么接下来BFS的核心很好处理了

检验函数，可以很好的避免堆栈溢出~~

 bool check(int z,int x,int y){

     return tz>= && tz<l && tx>= && tx<n && ty>= && ty<m;

 }

 que<pixel> vex;

 while(!que.empty()){

     pixel v = que.front();

     que.pop();

     for(int i=;i<;i++){

         int tz = v.z+z[i];    //求下个点

         int tx = v.x+x[i];

         int ty = v.y+y[i];

         check(tz,tx,ty) continue;

         if( vex[tz][tx][ty] ){ //可以到达

             que.push(vex[tz][tx][ty]);

         }

     }

 }

以上就是三维物体体积的BFS求解方式。之后再说一个个人观点，二维平面求不规则面积的问题似乎也可以用这种方式解决。

BFS在做层次遍历的时候我们要怎样记录各点所属的层呢？

 while(!que.empty()){

     vi = que.front();

     if(layer[vi] > maxlayer){

         maxlayer = layer[vi];    //BFS tree的深度

         index = ;    //初始化为极大

     }

     if(vi != v0){

         index = min(index,vi);    //最深那层中的编号最小的点

     }

     for(int i=;i<=n;i++){

         if(!visit[i] && v[vi][i] != ){

         visit[i] = true;

         layer[i] = layer[vi]+;    //进入了下一层，记录下i点所在的层数

         que.push(i);

         }

     }

     que.pop();

 }

以上代码是PAT中“喊山”一题的核心代码，很好的诠释了了BFS过程中层次的维护方法。

将来遇到了新问题还会作补充。。。

巴特西

简谈BFS

最新文章

热门文章