DFS与BFS算法详解：从基本概念到实际应用

DFS与BFS算法详解：从基本概念到实际应用

引用

CSDN

1.

https://m.blog.csdn.net/2401_82677021/article/details/145585131

DFS（深度优先搜索）和BFS（广度优先搜索）是图/树遍历的两种基础算法，核心在于探索顺序和适用场景的不同。本文将详细介绍这两种算法的基本概念、实现方式以及应用场景。

一、深度优先搜索（DFS）

1. DFS基本概念

DFS即Depth First Search，深度优先搜索。遍历顺序为：沿分支深入到底再回溯，优先探索最新发现的节点。简单来说，就是一条路走到黑。比如对下面一颗树的遍历。

从A开始遍历，再到B，有两种情况，意味着这条路还没有走完，接着走到D，之后就没路了。然后我就回溯到B，因为B还有情况没走完，接着再走到E，之后没路了，就回溯到B，发现B的两种情况以及那个走完了，就再回溯到A，然后走到C......

简单理解就是：一条路走动黑，直到没路可走了，再回溯回去，尝试其他路径。

2. 图的DFS遍历

DFS的实现方式有两种，一种是递归实现，但递归实现有时会产生栈溢出的风险，可改用显示栈实现。

(1) 递归实现（隐士栈）

#include <iostream>
#include <vector>
using namespace std;
void DFS(vector<vector<int>>& graph, int node, vector<bool>& visited)
{
    visited[node] = true;
    cout << node << " ";    //前序遍历
    for (int neighbors : graph[node])
    {
        if (!visited[neighbors])
            DFS(graph, neighbors, visited);
    }
}
int main()
{
    //邻接表表示(无向图）
    vector<vector<int>> graph = {
        {1,2},      //节点0的邻居是1 2
        {0,3,4},	//节点1的邻居是0 3 4
        {0,5},		//节点2的邻居是0 5
        {1},        //节点3的邻居是1
        {1},        //节点4的邻居是1
        {2}         //节点5的邻居是2
    };
    //记录访问过的节点
    vector<bool> visited(graph.size(), false);
    cout << "DFS结果为:";
    DFS(graph, 0, visited);
    return 0;
}  

(2) 显示栈实现（非递归）

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
void DFS_Stack(vector<vector<int>>& graph, int start)
{
    vector<bool> visited(graph.size(), false);
    stack<int> s;
    s.push(start);
    visited[start] = true;
    while (!s.empty())
    {
        int node = s.top();
        s.pop();
        cout << node << " ";
        //逆序入栈 以保证和递归顺序一致
        for (auto it = graph[node].rbegin(); it != graph[node].rend(); it++)
        {
            int neighbors = *it;
            if (!visited[neighbors])
            {
                visited[neighbors] = true;
                s.push(neighbors);
            }
        }
    }
}
int main()
{
    //邻接表表示(无向图）
    vector<vector<int>> graph = {
        {1,2},      //节点0的邻居是1 2
        {0,3,4},	//节点1的邻居是0 3 4
        {0,5},		//节点2的邻居是0 5
        {1},        //节点3的邻居是1
        {1},        //节点4的邻居是1
        {2}         //节点5的邻居是2
    };
    cout << "栈实现遍历结果为:" << endl;
    DFS_Stack(graph, 0);
    return 0;
}  

二、广度优先搜索（BFS）

1. BFS基本概念

BFS即Breadth First Search，即广度优先搜索。DFS是一条路走到黑，那么 BFS就可以理解成是在每个岔路口都向前走一步。也可以理解成是一层一层遍历。

从A开始遍历，有两种情况B，C。 将B，C遍历完后，再遍历D,E,F。一层一层的遍历。

上述是对树的BFS，然而树也是一种 图。 不难发现，我们每次搜索的位置都是离当前节点最近的点。因此，BFS是具有最短路性质的。这里用到的贪心策略是：想要找到最短路径，保证每次在选节点时，也就是每次前进的时候，都是距离上一个节点最近的点。

因此，BFS也可以求解最短路问题。

2. 图的BFS遍历

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
// BFS 遍历函数
void BFS(const vector<vector<int>>& graph, int start) {
    vector<bool> visited(graph.size(), false); // 访问标记数组
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " "; // 输出当前节点（可替换为自定义操作）
        // 遍历所有邻接节点
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}
int main() {
    // 示例图的邻接表表示（无向图）
    vector<vector<int>> graph = {
        {1, 2},     // 节点0的邻居是1和2
        {0, 3, 4},  // 节点1的邻居是0、3、4
        {0, 5},     // 节点2的邻居是0、5
        {1},        // 节点3的邻居是1
        {1},        // 节点4的邻居是1
        {2}         // 节点5的邻居是2
    };
    cout << "BFS遍历结果：";
    BFS(graph, 0); // 从节点0开始遍历
    // 输出：0 1 2 3 4 5 
    return 0;
}  

3. 路径记录

在图中寻找一条从开始到目标target的路径。

vector<int> BFS_Path(vector<vector<int>>& graph, int start, int target)
{
    vector<bool> visited(graph.size(), false);  //记录访问过的节点
    vector<int> parent(graph.size(), -1);  //记录父节点
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty())
    {
        int node = q.front();
        q.pop();
        if (node == target)
            break;
        for (int neighbors : graph[node])
        {
            if (!visited[neighbors])
            {
                visited[neighbors] = true;
                parent[neighbors] = node; //neighbors的父节点node
                q.push(neighbors);
            }
        }
    }
    vector<int> path;
    for (int at = target; at != -1; at = parent[at])
        path.push_back(at);
    reverse(path.begin(), path.end());
    return path;
}  

最短路径问题 （BFS）

【题目描述】

给的那个一个n*m的二维整数数组，用来表示迷宫，数组中只包含1和0，0表示可以走的路，1表示不可以通过的墙壁。

最初，有一个人位于左上角(1,1)处，已知改人每次可以向上，下，做，右任意一个方向移动一个位置。请问：改人从左上角移动到右下角(n,m），至少需要移动多少次。数据保证（0，0）和（n,m）的位置均为0。且一定至少存在一条通路。

【输入格式】

第一行包含两个整数n和m。

接下来n行，每行包含m个整数（0或1），表示迷宫。

【输出格式】

表示最少移动次数。

本题求的是最短路，所以可以用bfs从当前节点出发，每次向四周扩展。

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> PII;
//方向数组
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
const int N = 110;
int map[N][N];  //迷宫
int mark[N][N];  //标记数组
int n, m;
void BFS()
{
    memset(mark, -1, sizeof(mark));
    queue<PII> q;
    q.push({ 0,0 });
    mark[0][0] = 0;
    while (!q.empty())
    {
        PII top = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int x = top.first + dx[i];
            int y = top.second + dy[i];
            if (x >= 0 && x < n && y >= 0 && y < m && mark[x][y] == -1 && map[x][y] == 0)
            {
                q.push({ x,y });
                mark[x][y] = mark[top.first][top.second] + 1;
            }
        }
    }
    cout<<mark[n - 1][m - 1]<<endl;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> map[i][j];
    BFS();
    return 0;
}  

小结：

BFS优势与局限

• 优点：

• 保证找到最短路径（无权图）。

• 避免深度过大的栈溢出风险。

• 缺点：

• 空间消耗大（存储整层节点）。

• 不适合目标节点在深层的情况（效率低）。

DFS优势与局限

• 优点：

• 空间效率高（仅存储当前路径）。

• 适合寻找所有解（如回溯算法）。

• 缺点：

• 可能陷入无限深的分支（需设置最大深度）。

• 递归实现有栈溢出风险（可改用显式栈）。