BFS求解简单迷宫问题

（1）BFS遍历邻接矩阵：

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define MAXV 100//最大节点数
int visited[MAXV];
 
typedef struct{
    char vex[MAXV];//顶点表
    int edge[MAXV][MAXV];//邻接矩阵表
    int Vnum;//节点数
    int Enum;//边数
}MGraph;//无向图邻接矩阵结构
 
void CreateMG(MGraph *MG){
    int i,j,k;
    char v;
    cout<<"请依次输入顶点数和边数:";
    cin>>MG->Vnum>>MG->Enum;
    cout<<"请依次输入顶点:";
    for(i=0;i<MG->Vnum;i++)
        cin>>MG->vex[i];
    for(i=0;i<MG->Vnum;i++)//初始化邻接矩阵
        for(j=0;j<MG->Vnum;j++)
            MG->edge[i][j]=0;
    cout<<"请输入每条边对应的两个顶点下标(i,j):\n";
    for(k=0;k<MG->Enum;k++){
        cin>>i>>j;
        MG->edge[i][j]=1;
        MG->edge[j][i]=1;
    }
}//创建无向图邻接矩阵
 
void DisplayMG(MGraph MG){
    int i,j;
    for(i=0;i<MG.Vnum;i++){
        for(j=0;j<MG.Vnum;j++)
            cout<<MG.edge[i][j]<<' ';
        cout<<'\n';
    }
}//邻接矩阵输出无向图
 
void BfsMG(MGraph *MG,int v){
    queue<int>qu;//定义一个队列
    int w,i;
    cout<<v<<' ';//输出被访问顶点编号
    visited[v]=1;//置当前顶点为已访问状态
    qu.push(v);//顶点入队
    while(qu.empty()==0){
        w=qu.front();
        qu.pop();
        for(i=0;i<MG->Vnum;i++)
            if(MG->edge[w][i]==1&&visited[i]==0){//若当前相邻顶点i未被访问
                cout<<i<<' ';//访问相邻顶点
                visited[i]=1;//将相邻顶点设为已访问状态
                qu.push(i);//相邻顶点进队
            }
    }
    cout<<'\n';
}//BFS算法遍历邻接矩阵
 
int main(){
    MGraph g;
    CreateMG(&g);
    DisplayMG(g);
    memset(visited,0,sizeof(visited));//初始化visited数组
    cout<<"BFS遍历路径为:\n";
    BfsMG(&g,0);
}

（2）BFS遍历迷宫求解入口->出口路径：

#include<stdio.h>
#define MAX 10//迷宫最大长度
#define MAXV 100//顶点最大数量
int n=8;//迷宫实际大小
char Maze[MAX][MAX]= {
    {'O','X','X','X','X','X','X','X'},
    {'O','O','O','O','O','X','X','X'},
    {'X','O','X','X','O','O','O','X'},
    {'X','O','X','X','O','X','X','O'},
    {'X','O','X','X','X','X','X','X'},
    {'X','O','X','X','O','O','O','X'},
    {'X','O','O','O','O','X','O','O'},
    {'X','X','X','X','X','X','X','O'}
};
 
int H[4]= {0,1,0,-1}; //水平偏移量
int V[4]= {-1,0,1,0}; //垂直偏移量
 
struct Pos{
    int x,y;//当前方块坐标
    int pre;//前驱方块下标
};//队列元素结构
Pos qu[MAXV];//定义一个队列
int front=-1,rear=-1;//定义队头队尾
 
void DisplayPath(int front){
    int i,j;
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++)
            if(Maze[i][j]=='*')//恢复原状
                Maze[i][j]='O';
    }
    int k=front;//k设置为入口顶点
    while(k!=-1){
        Maze[qu[k].x][qu[k].y]='*';//将正确路径改为*
        k=qu[k].pre;
    }
    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
            printf("%c",Maze[i][j]);
        printf("\n");
    }
}//输出一条迷宫路径
 
void Bfs(int x,int y) {
    Pos p,p1,p2;
    p.x=x,p.y=y,p.pre=-1;//建立入口节点
    Maze[p.x][p.y]='*';
    rear++;
    qu[rear]=p;//入口结点进队
    while(front!=rear){//队不空时循环
        front++;
        p1=qu[front];//出队方块p1
        if(p1.x==n-1&&p1.y==n-1){//找到出口
            DisplayPath(front);//输出路径
            return;
        }
        for(int k=0;k<4;k++){
            p2.x=p1.x+V[k];
            p2.y=p1.y+H[k];
            if(p2.x>=0&&p2.y>=0&&p2.x<n&&p2.y<n&&Maze[p2.x][p2.y]=='O'){
                Maze[p2.x][p2.y]='*';//将当前路径改为*
                p2.pre=front;
                rear++;
                qu[rear]=p2;//方块p2进队
            }
        }
    }
 
}//从(x,y)点开始遍历迷宫
 
 
int main() {
    int x=0,y=0;//入口坐标
    printf("一条迷宫路径为:\n");
    Bfs(x,y);
}

-------该算法摘自《算法设计与分析(第2版)》