BFS实现迷宫最短路径

    结合队列的知识利用 广度优先遍历，通过对能走的路径的记录以及对走过路径的标记，进行多条路搜查

一、理论基础

如下图的迷宫：

        选取所走方向（针对某一个位置）下，右，上，左，从起点（0,0）开始进行广度搜索，标记（0,1）走过，重复寻路，直到走到终点

如图：

        通过一个点找到所有与该顶点相连且能走的顶点，不停寻找，直到找到目的地或走完所有能走的点为止，图中可以看到

        任意一个顶点只有一个前驱，可以通过某种方式记录该顶点的前驱，一步步回到原点，并记录移动轨迹，最终得到从起点到终点最短路径的数组

步骤：

1）起点入队

2）队头出队，

3）找到所有与队头相连且为空地的点，将这些点都入队，并记录这些点的前驱

4）重复执行步骤2）3），直到队列为空

5）通过终点一步步回到前驱，最终回到终点，得到最短路径\

二、代码实现

C语言代码实现如下：

① 定义坐标结构体

typedef struct
{int row;	//行int col;	//列	
}Position;

② 定义队列结构及操作

typedef struct
{Position*queue;	//队列int front;		//头部int rear;		//尾部int cap;		//队列容量
}MyQueue;//判断队列是否已满
bool IsEmpty(MyQueue*myqueue)
{if(myqueue->front==myqueue->rear)return true;elsereturn false;
}
//弹出队头
Position PopFront(MyQueue*myqueue)
{Position p=myqueue->queue[myqueue->front];myqueue->front=(myqueue->front+1)%myqueue->cap;return p;
}
//插入队尾
void PushRear(MyQueue*myqueue,Postion p)
{myqueue->queue[myqueue->rear]=p;myqueue->rear=(myqueue->rear+1)%myqueue->cap;
}

③ 设置移动方向 

//移动方向
int orient[4][2]={{1,0},{0,1},{-1,0},{0,-1}//下    右     上     左
}

④ 开始广度寻路 

//0代表空地，1代表墙
void ShortestPath_BFS(int**maze,int maze_row,int maze_col,Position start,Position destination)
{//创建队列MyQueue*myqueue=CreatMyQueue(maze_row*maze*col);/*创建vt数组，标记某些点是否走过，0代表未走过，非0代表走过（1代表该点的前驱在该点下方，2代表该点的前驱在该点右边，3代表上，4代表左）*/int vt[maze_row][maze_col];memset(vt,0,sizeof(vt));	//对所有点初始化标记为未走过PushRear(myqueue,start);	//起点入队vt[start.row][start.col]=5;	//标记起点已走过，5代表起点位置while(!IsEmpty(myqueue)){Position temp=PopFront(myqueue);	//队头出队//找到与出队顶点相连且为空地的所有顶点入队for(int ori=0;ori<4;ori++){//定义试探点int newRow=temp.row+orient[i][0];int newCol=temp.col+orient[i][1];//判断试探点是否能走if(newRow>=0&&newRow<maze_row&&newCol>=0&&newCol<maze_col&&maze[newRow][newCol]==0&&vt[newRow][newCol]==0)//不越界，且为空地，未走过{//该点入队Position p;p.row=newRow;p.col=newCol;PushRear(queue,p);//标记该点走过,记录该点前驱方向vt[newRow][newCol]=(ori+2)%4+1;}}}//定义路径数组Position*path=malloc(sizeof(Position)*maze_row*maze_col);int path_size=0;//通过终点回到前驱，直到回到起点，记录其移动轨迹int curRow=destination.row;int curCol=destination.col;while(vt[curRow][curCol]!=5){path[path_size].row=curRow;path[path_size].col=curCol;path_size++;int ori=vt[curRow][curCol]-1;//前驱点相对于该点的方向在orient数组中的位置curRow+=orient[ori][0];		//前驱点的行curCol+=orient[ori][1];		//前驱点的列}//将起点位置存入路径数组path[path_size].row=start.row;path[path_size].col=start.col;path_size++;//展示从起点开始到终点的路径for(int i=path_size-1;i>=0;i--){printf("(%d,%d)"path[i].row,path[i].col);if(i!=0)printf("->");}
}