前言

又有好长一段时间没有水过文章了，上次水还是在上次.
DFS和BFS是最基本的暴力算法，大多用于解决图、树的遍历问题。

在写(水)这篇文章的过程中突然灵感迸发，想到一些浪漫且Emo的话，在此记录下来:

我不会用高效的Dijkstra,只能笨拙地用DFS不断探索,寻找能抵达你内心的路径。哪怕途中会撞得遍体鳞伤,哪怕最糟情况下会浪费最多的时间,我也在所不惜。因为对我而言,能最终抵达你的内心,与你并肩同行,就是这条漫漫长路上最浪漫、最完美的风景。

--GuWolf

算法差异

DFS(深度优先算法): 一路走到底，走完(撞墙) 才回头(回溯)，也就是不撞南墙不回头。
BFS(广度优先算法): 层层递进，一层一层的递进搜索 (可以理解为模拟并行计算)。

DFS

DFS基于栈结构(后进先出)，主要使用递归实现。一条路走到底，直到达到终点或撞墙，撞墙则回溯上一点，走其他方向，如果其他方向也无法到达终点，则再回溯上一点，以此类推。
下面给出一道非常简单的变种DFS题目，旨在帮助你理解DFS的递归与回溯
题目链接: https://vj.guwolf.com/problem/CodeForces-1097B#author=GPT_zh

#include <bits/stdc++.h>
using namespace std; 

int a[16], flag = 0, n;

void DFS(int sum, int deep) {
    if (flag) return; 
    if (deep == n + 1) {//到最后一个数时，检查结果能否被360整除 
        if (sum % 360 == 0) flag = 1;
        return;
    }
    
    DFS(sum + a[deep], deep + 1);
    DFS(sum - a[deep], deep + 1); //不是加就是减 
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    DFS(0, 0);
    if (flag) cout << "YES";
    else cout << "NO";
    return 0;
}

BFS

BFS主要用到的数据结构是队列(先进先出)，从队列里弹出前面的点，并把该点周围的未途经点入队。
详见下图及介绍

1. 先把最开始的点(1)入队
2. 从队里取出(1) 并 把周围未经点 (2)、(3) 入队
3. 从队里取出(2) 并把周围未经点 (4) 入队
4. 从队里取出(3) 并把周围未经点 (5) 入队 ......

队列情况:
{1}
{1,2,3}
{2,3,4,5}
{4,5,6,7,8,9}
{6,7,8,9,10,11}
{10,11,12,13}
{12,13}
{} //队列为空，结束

代码实现

#include <bits/stdc++.h> //万能头文件
using namespace std;

bool vis[6][6]; //用于记录是否到达过 
int x[4] = {0,0,-1,1}, y[4] = {1,-1,0,0}; //用于移动
struct node {
    int x, y;
} ;

void bfs() {
    node now, temp;
    vis[1][1] = now.x = now.y = 1;
    queue <node> q;
    q.push(now);
    while(!q.empty()) {
        now = q.front();
        q.pop(); // 出队 
        cout << now.x << ' ' << now.y << endl;
        for (int i = 0; i < 4; ++i) {
            temp.x = now.x + x[i], temp.y = now.y + y[i]; // 下一个点 
            if (!vis[temp.x][temp.y] && temp.x >= 1 && temp.x <= 4 && temp.y >= 1 && temp.y <= 4) { // 满足条件入队 
                vis[temp.x][temp.y] = 1;
                q.push(temp); 
            }
        }
    }
} 

int main() {
    vis[2][2] = vis[3][3] = 1; //两个障碍，仅做演示用，将就看 
    bfs();
    return 0; //好习惯 
} 

运行结果