DFS求解简单迷宫问题

（1）DFS遍历邻接矩阵：

#include<iostream>
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 DfsMG(MGraph *MG,int v){
    int w;
    cout<<v<<' ';//输出被访问顶点
    visited[v]=1;//将当前顶点设为已访问状态
    for(w=0;w<MG->Vnum;w++)
        if(MG->edge[v][w]==1&&visited[w]==0)
            DfsMG(MG,w);//查找顶点v的未访问的相邻点
}
 
int main(){
    MGraph g;
    CreateMG(&g);
    DisplayMG(g);
    cout<<"DFS遍历路径为:\n";
    DfsMG(&g,0);
}

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

#include<stdio.h>
#define MAX 10
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}; //垂直偏移量
 
 
void DisplayPath() {
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++)
            printf("%c",Maze[i][j]);
        printf("\n");
    }
}//输出一条迷宫路径
 
 
void Dfs(int x,int y) {
    if(x==n-1&&y==n-1) { //找到出口并结束遍历输出
        Maze[n-1][n-1]='?';
        DisplayPath();
        return;
    } else {
        for(int k=0; k<4; k++) {
            if(x>=0&&y>=0&&x<n&&y<n&&Maze[x][y]=='O') {
                Maze[x][y]='*';//标记走过的路径
                Dfs(x+V[k],y+H[k]);
                Maze[x][y]='O';
            }
        }
    }
}//从(x,y)点开始遍历迷宫
 
 
int main() {
    int x=0,y=0;//入口坐标
    printf("一条迷宫路径为:\n");
    Dfs(x,y);
}

DFS遍历邻接表实在太麻烦(报了一堆错)，所以放弃了。

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