设为首页 加入收藏

TOP

BFS(三):双向广度优先搜索(四)
2019-07-09 16:10:26 】 浏览:270
Tags:BFS 双向 广度 优先 搜索
采用双向搜索,如何知道某个结点是正向还是逆向扩展来的呢?

       简单修改vis[][]数组元素的置值方法即可。初始时,vis数组的全部元素值为0,由正向扩展来的结点的vis对应元素值置为1,由逆向扩展来的结点的vis对应元素值置为2。

      设当前结点为cur,由cur可以扩展出新结点next。若vis[next.x][next.y]==0,则next结点未访问过,将next结点入队并进行相应设置;若vis[next.x][next.y]!=0,则next结点已访问过。由于vis[cur.x][cur.y]记录的是当前扩展方向(1代表正向,2代表逆向),若vis[next.x][next.y] != vis[cur.x][cur.y],则表示next结点以前按相反的方向访问过,正向和反向遇到了同一个结点,搜索成功。

      (4)采用双向广度优先搜索的源程序。

#include <stdio.h>

int vis[305][305], step[305][305];

int dx[] = {-2, -2, -1, 1, 2, 2, 1, -1};

int dy[] = {-1, 1, 2, 2, 1, -1, -2, -2};

struct point

{

     int x, y;

};

int BFS(int start_x,int start_y,int end_x,int end_y,int n)

// 在n*n的棋盘中搜索从起点(start_x,strat_y)到终点(end_x,end_y)所需的最少步数

{

     int front,rear,i;

      point cur,next,q[90005];

      front=rear=0;

     cur.x = start_x;

     cur.y = start_y;

     vis[start_x][start_y] = 1;  // 从起始位置开始的探索标记为1

     q[rear++] = cur;         // 起始坐标入队

     next.x = end_x;

     next.y = end_y;

     vis[end_x][end_y] = 2;   // 从终点位置开始的探索标记为 2

     q[rear++] = next;    // 终点坐标入队

     while (front < rear)

     {

         cur = q[front++];     /* 队首结点坐标出队 */

         for (i=0; i<8; ++i)

         {

             next.x = cur.x + dx[i];

             next.y = cur.y + dy[i];

             if (next.x<0 || next.x>=n || next.y<0 || next.y>=n)

                 continue;

             if (!vis[next.x][next.y])

             {

                 vis[next.x][next.y] = vis[cur.x][cur.y];     // 设为与当前探索路径相同的标记

                 step[next.x][next.y] = step[cur.x][cur.y] + 1; // 记录步数

                 q[rear++] = next; // 当前合法坐标位置入队

             }

             else if (vis[cur.x][cur.y] != vis[next.x][next.y])

             {   // 说明从起点出发的探索与从终点出发的探索重合

          &nbs

首页 上一页 1 2 3 4 5 6 下一页 尾页 4/6/6
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇基数排序的可复用实现(C++11/14/.. 下一篇DFS(三):八皇后问题

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目