数据结构实践——迷宫问题之图深度优先遍历解法

偏执的太偏执、 2022-04-17 04:13 186阅读 0赞

**分享一下我老师大神的人工智能教程！零基础，通俗易懂！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow]**

**也欢迎大家转载本篇文章。分享知识，造福人民，实现我们中华民族伟大复兴！**

本文是针对\[[数据结构基础系列(7)：图][7]\]的实践项目。

【项目 - 迷宫问题之图深度优先遍历解法】  
　　设计一个程序，采用深度优先遍历算法的思路，解决迷宫问题。  
　　（1）建立迷宫对应的图数据结构，并建立其邻接表表示。  
　　（2）采用深度优先遍历的思路设计算法，输出从入口(1,1)点到出口(M,N)的所有迷宫路径。

\[模型建立\]  
　　将迷宫中的每一格作为一个顶点，相邻格子可以到达，则对应的顶点之间存在边相连。  
　　例如，下面的迷宫  
![这里写图片描述][20151108152346516]  
在使用数组表示时，用０表示格子是空地，用１表示格子处是墙，对应的矩阵是：

int mg[M+2][N+2]=   //迷宫数组    {        {1,1,1,1,1,1},        {1,0,0,0,1,1},        {1,0,1,0,0,1},        {1,0,0,0,1,1},        {1,1,0,0,0,1},        {1,1,1,1,1,1}    };
      
       
        1 
        2 
        3 
        4 
        5 
        6 
        7 
        8 
        9

建立的图结构为：  
![这里写图片描述][20151108153255700]  
于是，从(1,1)到(4,4)的迷宫问题，转化为寻找顶点(1,1)到顶点(4,4)的路径的问题。

\[参考代码\]

#include <stdio.h>#include <malloc.h>#define MaxSize 100#define M 4#define N 4//以下定义邻接表类型typedef struct ANode            //边的结点结构类型{    int i,j;                    //该边的终点位置(i,j)    struct ANode *nextarc;      //指向下一条边的指针} ArcNode;typedef struct Vnode            //邻接表头结点的类型{    ArcNode *firstarc;          //指向第一条边} VNode;typedef struct{    VNode adjlist[M+2][N+2];    //邻接表头节点数组} ALGraph;                      //图的邻接表类型typedef struct{    int i;                      //当前方块的行号    int j;                      //当前方块的列号} Box;typedef struct{    Box data[MaxSize];    int length;                 //路径长度} PathType;                     //定义路径类型int visited[M+2][N+2]= {
        0};int count=0;void CreateList(ALGraph *&G,int mg[][N+2])//建立迷宫数组对应的邻接表G{    int i,j,i1,j1,di;    ArcNode *p;    G=(ALGraph *)malloc(sizeof(ALGraph));    for (i=0; i<M+2; i++)                   //给邻接表中所有头节点的指针域置初值        for (j=0; j<N+2; j++)            G->adjlist[i][j].firstarc=NULL;    for (i=1; i<=M; i++)                    //检查mg中每个元素        for (j=1; j<=N; j++)            if (mg[i][j]==0)            {                di=0;                while (di<4)                {                    switch(di)                    {                    case 0:                        i1=i-1;                        j1=j;                        break;                    case 1:                        i1=i;                        j1=j+1;                        break;                    case 2:                        i1=i+1;                        j1=j;                        break;                    case 3:                        i1=i, j1=j-1;                        break;                    }                    if (mg[i1][j1]==0)                          //(i1,j1)为可走方块                    {                        p=(ArcNode *)malloc(sizeof(ArcNode));   //创建一个节点*p                        p->i=i1;                        p->j=j1;                        p->nextarc=G->adjlist[i][j].firstarc;   //将*p节点链到链表后                        G->adjlist[i][j].firstarc=p;                    }                    di++;                }            }}//输出邻接表Gvoid DispAdj(ALGraph *G){    int i,j;    ArcNode *p;    for (i=0; i<M+2; i++)        for (j=0; j<N+2; j++)        {            printf("  [%d,%d]: ",i,j);            p=G->adjlist[i][j].firstarc;            while (p!=NULL)            {                printf("(%d,%d)  ",p->i,p->j);                p=p->nextarc;            }            printf("\n");        }}void FindPath(ALGraph *G,int xi,int yi,int xe,int ye,PathType path){    ArcNode *p;    visited[xi][yi]=1;                   //置已访问标记    path.data[path.length].i=xi;    path.data[path.length].j=yi;    path.length++;    if (xi==xe && yi==ye)    {        printf("  迷宫路径%d: ",++count);        for (int k=0; k<path.length; k++)            printf("(%d,%d) ",path.data[k].i,path.data[k].j);        printf("\n");    }    p=G->adjlist[xi][yi].firstarc;  //p指向顶点v的第一条边顶点    while (p!=NULL)    {        if (visited[p->i][p->j]==0) //若(p->i,p->j)方块未访问,递归访问它            FindPath(G,p->i,p->j,xe,ye,path);        p=p->nextarc;               //p指向顶点v的下一条边顶点    }    visited[xi][yi]=0;}int main(){    ALGraph *G;    int mg[M+2][N+2]=                           //迷宫数组    {        {
        1,1,1,1,1,1},        {
        1,0,0,0,1,1},        {
        1,0,1,0,0,1},        {
        1,0,0,0,1,1},        {
        1,1,0,0,0,1},        {
        1,1,1,1,1,1}    };    CreateList(G,mg);    printf("迷宫对应的邻接表:\n");    DispAdj(G); //输出邻接表    PathType path;    path.length=0;    printf("所有的迷宫路径:\n");    FindPath(G,1,1,M,N,path);    return 0;}
      
       
        1 
        2 
        3 
        4 
        5 
        6 
        7 
        8 
        9 
        10 
        11 
        12 
        13 
        14 
        15 
        16 
        17 
        18 
        19 
        20 
        21 
        22 
        23 
        24 
        25 
        26 
        27 
        28 
        29 
        30 
        31 
        32 
        33 
        34 
        35 
        36 
        37 
        38 
        39 
        40 
        41 
        42 
        43 
        44 
        45 
        46 
        47 
        48 
        49 
        50 
        51 
        52 
        53 
        54 
        55 
        56 
        57 
        58 
        59 
        60 
        61 
        62 
        63 
        64 
        65 
        66 
        67 
        68 
        69 
        70 
        71 
        72 
        73 
        74 
        75 
        76 
        77 
        78 
        79 
        80 
        81 
        82 
        83 
        84 
        85 
        86 
        87 
        88 
        89 
        90 
        91 
        92 
        93 
        94 
        95 
        96 
        97 
        98 
        99 
        100 
        101 
        102 
        103 
        104 
        105 
        106 
        107 
        108 
        109 
        110 
        111 
        112 
        113 
        114 
        115 
        116 
        117 
        118 
        119 
        120 
        121 
        122 
        123 
        124 
        125 
        126 
        127 
        128 
        129 
        130 
        131 
        132 
        133 
        134 
        135 
        136 
        137 
        138 
        139 
        140 
        141 
        142 
        143 
        144 
        145

测试时，换作下面的迷宫试一试：  
![这里写图片描述][20151108153606661]

#### 给我老师的人工智能教程打call！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow] ####

![这里写图片描述][SouthEast]

[http_blog.csdn.net_jiangjunshow]: https://blog.csdn.net/jiangjunshow/article/details/77338485
[7]: http://edu.csdn.net/course/detail/1595
[20151108152346516]: /images/20220417/d67a8757dd15407b9dd1d2ebeb0c9b5b.png
[20151108153255700]: /images/20220417/32aa9878401842c4b837364adbd649a8.png
[20151108153606661]: /images/20220417/86de0dac277242afa56e3826d75f07bc.png
[SouthEast]: /images/20220417/cd297d07ebd24c2294a3c32796feff12.png