简单通俗上手BFS(广度优先搜索)与DFS(深度优先搜索)_bfs和dfs内存占用

重新复习BFS和DFS，记录一下。思路简单，注释比较详细，希望能和大家互相交流学习。好啦~~~下面开始进入正题。

广度优先搜索(BFS)和深度优先搜索(DFS)是两种常见的搜索算法，它们在处理数据和解决问题时各有优势，适用于不同的情况。

BFS与DFS的介绍

BFS:
1.BFS的思想是从初始状态开始，逐层向外搜索，直到找到目标状态。
2.BFS在搜索过程中会记录已访问过的状态，避免重复访问。
3.BFS占用的内存较多，但速度较快。
4.对于那些对程序运行效率要求较高，或者需要找出最短路径的问题，通常会选择广度优先搜索。此外，如果数据量较小，对内存空间的需求相对较低，那么广度优先搜索也是一个很好的选择。
5.队列，先进先出

DFS:
1.DFS的思想是从初始状态出发，不断向前探索，直到达到目标位置。如果当前路径无法继续前进，它会回退一步并尝试其他路径。这个过程一直进行，直到所有与初始状态有路径相通的状态都被访问到。
2.DFS占用的内存较少，但速度较慢。在内存不够大时，为了防止内存溢出，通常会选择DFS。
3.如果问题的递归形式较为明显，DFS也是一个很好的选择，因为递归方法可以使得程序结构更简捷易懂。然而，当搜索深度较大时，由于系统堆栈容量的限制，递归易产生溢出，这时非递归方法的设计更为合适。
4.栈，先进后出

总结

广度优先搜索和深度优先搜索各有其优点和适用情况。BFS(广度优先搜索)则适用于需要快速找出最优解、数据量较大或对程序运行效率要求较高，而DFS(深度优先搜索)在内存需求较低、问题具有明显的递归形式或深度较浅时具有优势的情况。在具体应用中，应根据问题的特点来选择合适的搜索算法。

代码

#include <iostream>
#include <algorithm>
#include <queue>
/*输入：
5 4
1 1 0 1
0 1 1 0
0 1 1 1
0 0 1 1
0 1 1 1
*/
using namespace std;
const int N=1020;
int t[N][N];
int vis[N][N];
bool dfs_flag;
int n,m;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
///
struct node{
    int x,y;//记录初始状态
    int l;//记录该位置是第几次发散，即路径长度
};
queue <node> q;
int road_x[N][N],road_y[N][N];//记录此位置的上一个位置，以输出路径
//dfs是栈，先进后出
void dfs(int x,int y,int step)//x y为起始位置，step为走的步数
{
    /*if(dfs_flag==true)//找到一个就结束，如果不写这个的话就把所有结果都找到
    {
        return ;
    }*/
    //vis[x][y]=1;这样只能找到一个，因为没有把从下一步回来的vis设成0
    if(x==n&&y==m)
    {
        dfs_flag=true;
        cout<<"dfs_Success,步数为"<<step<<"并输出路径为:"<<"[1,1]";
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(vis[i][j]==1)
                cout<<"->["<<i<<","<<j<<"]";
            }
        }
        cout<<endl;
        return ;
    }
    for(int i=0;i<4;i++)//向四周找是否有路可走
    {
        int next_x=x+dx[i],next_y=y+dy[i];//尝试所有方向
        if(next_x<1 || next_x>n ||next_y<1 ||next_y>m)//判断是否超出边界
        {
            continue;//换一个方向
        }
        //如果没有被访问且当前位置有路
        if(vis[next_x][next_y]==0 &&t[next_x][next_y]==1)
        {
            vis[next_x][next_y]=1;
            dfs(next_x,next_y,step+1);
            vis[next_x][next_y]=0;
        }
    }

}
void output_bfs(int x,int y)
{
    if(road_x[x][y]==1 && road_y[x][y]==1)
    {
        cout<<"[1,1]";
        return ;
    }
    else
    {
        output_bfs(road_x[x][y],road_y[x][y]);
        cout<<"->["<<road_x[x][y]<<","<<road_y[x][y]<<"]";
    }
}
//bfs是队列，先进先出
void bfs()
{
    q.push((node){1,1,0});
    while(!q.empty())
    {
        node now =q.front();//取队首状态
        vis[now.x][now.y]=1;
        //cout<<"x:"<<now.x<<"y:"<<now.y<<endl;
        q.pop();//将队首移出队列
        if(now.x==n &&now.y==m)//到达终点
        {
            cout<<"bfs_Success,步数为"<<now.l<<"并输出路径为:";
            output_bfs(n,m);
            cout<<"->["<<n<<","<<m<<"]"<<endl;
            break;
        }
        //下面与dfs中的判断条件类似
        for(int i=0;i<4;i++)//向四周找是否有路可走
        {
            int next_x=now.x+dx[i],next_y=now.y+dy[i];//尝试所有方向
            if(next_x<1 || next_x>n ||next_y<1 ||next_y>m)//判断是否超出边界
            {
                continue;//换一个方向
            }
            //如果没有被访问且当前位置有路
            if(vis[next_x][next_y]==0 &&t[next_x][next_y]==1)
            {
                road_x[next_x][next_y]=now.x;
                road_y[next_x][next_y]=now.y;
                q.push((node){next_x,next_y,now.l+1});//把下一步放入队列中
            }
        }
    }
    return ;
}
int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>t[i][j];
        }
    }
    dfs(1,1,0);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            vis[i][j]=0;
        }
    }
   bfs();

}

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