深度优先与广度优先搜索求解迷宫寻路

谁借莪１个温暖的怀抱￠ 2023-07-24 08:56 18阅读 0赞

### 深度优先与广度优先搜索求解迷宫寻路 ###

*  算法比较
 *  广度优先搜索（队列）
 *  深度优先搜索加回溯法（栈）
 *   *  求解第一条可行路径
     *  求解最短路径

# 算法比较 #

第一种方法：广度优先搜索（BFS）。  
优点： 找出的第一条路径就是最短路径。  
缺点： 需要记录结点的前驱结点，来形成路径。

第二种方法：深度优先搜索（DFS）加回溯。  
优点： 无需像广度优先搜索那样（BFS）记录前驱结点。  
缺点： 找到的第一条可行路径不一定是最短路径，如果需要找到最短路径，那么需要找出所有可行路径后，再逐一比较，求出最短路径。

# 广度优先搜索（队列） #

广度优先搜索的优点是找出的第一条路径就是最短路径，所以经常用来搜索最短路径，思路和图的广度优先遍历一样，需要借助队列。  
[最初代码：https://blog.csdn.net/p1967914901/article/details/105394590][https_blog.csdn.net_p1967914901_article_details_105394590]  
**【实现原理】**  
（1）从入口元素开始，判断它上下左右的邻边元素是否满足条件，如果满足条件就入队列；  
（2）取队首元素并出队列。寻找其相邻未被访问的元素，将其如队列并标记元素的前驱节点为队首元素；  
（3）重复步骤（2），直到队列为空（没有找到可行路径）或者找到了终点。最后从终点开始，根据节点的前驱节点找出一条最短的可行路径。  
**输入：**

8 8	
    0 0 1 0 0 0 1 0
    0 0 1 0 0 0 1 0
    0 0 0 0 1 1 0 0
    0 1 1 1 0 0 0 0
    0 0 0 1 0 0 0 0
    0 1 0 0 0 1 0 0
    0 1 1 1 0 1 1 0
    1 0 0 0 0 0 0 0

**输出：**

1,1
    2,1
    3,1
    4,1
    5,1
    5,2
    5,3
    6,3
    6,4
    6,5
    7,5
    8,5
    8,6
    8,7
    8,8

**【程序实现】**

#include<bits/stdc++.h>
    using namespace std;
    struct site{
        
    	int x,y;
        struct site *next;
    }p[100],link[100][100];//将到终点的路线逆向保存
    struct site *head, *rear;//分别指向链队列的头和尾
    int main(){
        
    	int m, n, a[100][100], flag = 1; 
        int move[4][2] = {
         {
        1,0} , {
        0,1} , {
        -1,0} , {
        0,-1} };//用二维数组分别表示下右上左
        head = new struct site;
        rear = head;
        rear->next = NULL;
    	cin>>m>>n;//输入M和N值，表示迷宫行数和列数。
        struct site *temp;
        for(int i = 1; i <= m; i++) 
            for (int j = 1; j <= n; j++)
                cin>>a[i][j];
        for(int i = 1; i <= m; i++) {
        //将周围用墙围起来
            a[i][0] = 1;
            a[i][n+1] = 1;
        }
        for (int j = 1; j <= n; j++){
        //将周围用墙围起来
            a[0][j] = 1;
            a[m+1][j] = 1;
        }
        head->x = 1;
        head->y = 1;
        a[1][1] = 6;//搜索过的地方值变为6
        while(head){
        
            temp = head;
            head = head->next;
            int x = temp->x, y = temp->y;
            if(x == m && y == n) {
        //如果找到终点
                flag = 0;
                int k = 0;
                p[k++] = *temp;
                while(temp->x != 1 || temp->y != 1){
        //将到终点的路线逆向保存
                    p[k++] = link[temp->x][temp->y];
                    *temp = link[temp->x][temp->y];
                }
                for(int i = k-1; i >= 0; i--)//输出路线
                    cout<<p[i].x<<','<<p[i].y<<endl;
                break;
            }
            for (int w = 0; w < 4; w++) {
        //遍历四个方向
                temp->x = x + move[w][0];
                temp->y = y + move[w][1];
                if(a[temp->x][temp->y] == 0){
        
                    if(head == NULL) {
        
                        head = rear = new struct site;
                        *head = *temp;
                        head->next = NULL;
                    }
                    else{
        
                        rear->next = new struct site;
                        *(rear->next) = *temp;
                        rear = rear->next;
                        rear->next = NULL;
                    } 
                    a[temp->x][temp->y] = 6;//搜索过的地方值变为6
                    link[temp->x][temp->y].x = x;
                    link[temp->x][temp->y].y = y;
                }
            }
        }
        if(flag)
            cout<<"NO FOUND"<<endl;
    	return 0;
    }

# 深度优先搜索加回溯法（栈） #

## 求解第一条可行路径 ##

实现步骤：  
（1）给定起点和终点，判断二者的合法性，如果不合法，返回；  
（2）如果起点和终点合法，将起点入栈；  
（3）取栈顶元素，求其邻接的未被访问的无障碍结点。求如果有，记其为已访问，并入栈。如果没有则回溯上一结点，具体做法是将当前栈顶元素出栈。其中，求邻接无障碍结点的顺序可任意，本文实现是以下、右、上、左的顺序求解。  
（4）重复步骤（3），直到栈空（没有找到可行路径）或者栈顶元素等于终点（找到第一条可行路径）。  
**【程序实现】**

#include<bits/stdc++.h>
    using namespace std;
    struct site{
        
    	int x,y;
    }p[100],link[100][100],stk[1000];//将到终点的路线逆向保存
    int top = -1;//栈顶指针
    int main(){
        
    	int m, n, a[100][100], flag = 1; 
        int move[4][2] = {
         {
        1,0} , {
        0,1} , {
        -1,0} , {
        0,-1} };//用二维数组分别表示下右上左
    	cin>>m>>n;//输入M和N值，表示迷宫行数和列数。
        for(int i = 1; i <= m; i++) 
            for (int j = 1; j <= n; j++)
                cin>>a[i][j];
        for(int i = 1; i <= m; i++) {
        //将周围用墙围起来
            a[i][0] = 1;
            a[i][n+1] = 1;
        }
        for (int j = 1; j <= n; j++){
        //将周围用墙围起来
            a[0][j] = 1;
            a[m+1][j] = 1;
        }
        stk[++top].x = 1;
        stk[top].y = 1;
        a[1][1] = 6;//搜索过的地方值变为6
        while(top != -1){
        
            struct site temp = stk[top--];//出栈
            int x = temp.x, y = temp.y;
            if(x == m && y == n) {
        //如果找到终点
                int k = 0;
                p[k++] = temp;
                while(temp.x != 1 || temp.y != 1){
        //将到终点的路线逆向保存
                    p[k++] = link[temp.x][temp.y];
                    temp = link[temp.x][temp.y];
                }
                for(int i = k-1; i >= 0; i--)//输出路线
                    cout<<p[i].x<<','<<p[i].y<<endl;
                break;
            }
            for (int w = 0; w < 4; w++) {
        //遍历四个方向
                temp.x = x + move[w][0];
                temp.y = y + move[w][1];
                if(a[temp.x][temp.y] == 0){
        
                    stk[++top] = temp;
                    a[temp.x][temp.y] = 6;//搜索过的地方值变为6
                    link[temp.x][temp.y].x = x;
                    link[temp.x][temp.y].y = y;
                }
            }
        }
        if(top == -1)
            cout<<"NO FOUND"<<endl;
    	return 0;
    }

**【输入同上】**  
**【输出】**

1,1
    1,2
    2,2
    3,2
    3,1
    4,1
    5,1
    5,2
    5,3
    6,3
    6,4
    6,5
    5,5
    4,5
    4,6
    4,7
    4,8
    5,8
    6,8
    7,8
    8,8

事实上还有比这个更短的路径

## 求解最短路径 ##

未完待续。。。。。

[https_blog.csdn.net_p1967914901_article_details_105394590]: https://blog.csdn.net/p1967914901/article/details/105394590