• C++

  • 算法：深度优先遍历和广度优先遍历

  • @ 2025-8-22 20:05:27

算法：深度优先遍历和广度优先遍历

https://blog.csdn.net/zhizhengguan/article/details/122468043

2 条评论

  • @ 2025-8-22 20:16:40

    深度优先遍历（DFS）与广度优先遍历（BFS）零基础教程（C++实现）

    遍历是图论和树结构中的核心操作，指从指定起点出发，按照某种规则访问所有可达节点且不重复访问的过程。深度优先遍历（DFS）和广度优先遍历（BFS）是两种最基础、最常用的遍历算法，广泛应用于路径搜索、拓扑排序、连通性判断等场景。本教程从0基础出发，先讲解理论原理，再结合C++代码实现，帮助你彻底掌握这两种算法。

    一、前置知识：图与树的存储方式

    在学习遍历算法前，需先掌握“如何用代码存储图/树”。因为遍历的对象是“节点”和“边”，必须先将这些结构转化为计算机可理解的数据格式。以下是两种最常用的存储方式（以无向图为例，有向图仅需调整边的存储方向）：

    1. 邻接矩阵（Adjacency Matrix）

    • 原理：用一个n x n的二维数组graph存储图，其中n是节点总数。若节点i和节点j之间有边，则graph[i][j] = 1（或边的权重）；若无边，则graph[i][j] = 0。
    • 优点：判断两个节点是否相邻的时间复杂度为O(1)，实现简单。
    • 缺点：空间复杂度为O(n²)，节点数量大（如n>1000）时会严重浪费内存。
    • 适用场景：节点数量少（n≤1000）的稠密图（边数接近n²）。

    C++实现示例：

    #include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 5; // 节点数（假设节点编号0~4）
    vector<vector<int>> adjMatrix(n, vector<int>(n, 0)); // 初始化n x n矩阵，默认0
    
    // 添加边：0-1, 0-2, 1-3, 2-3, 3-4
    adjMatrix[0][1] = 1;
    adjMatrix[1][0] = 1; // 无向图，边双向存储
    adjMatrix[0][2] = 1;
    adjMatrix[2][0] = 1;
    adjMatrix[1][3] = 1;
    adjMatrix[3][1] = 1;
    adjMatrix[2][3] = 1;
    adjMatrix[3][2] = 1;
    adjMatrix[3][4] = 1;
    adjMatrix[4][3] = 1;
    
    // 打印邻接矩阵
    cout << "邻接矩阵：" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << adjMatrix[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

    2. 邻接表（Adjacency List）

    • 原理：用一个长度为n的数组（或向量）存储图，数组的每个元素是一个链表（或向量），存储该节点的所有“邻居节点”（即与该节点直接相连的节点）。
    • 优点：空间复杂度为O(n + m)（m是边数），仅存储实际存在的边，适合稀疏图（边数远小于n²）。
    • 缺点：判断两个节点是否相邻需遍历链表，时间复杂度为O(degree(i))（degree(i)是节点i的度数，即邻居数）。
    • 适用场景：节点数量大（n>1000）的稀疏图，也是实际开发中最常用的存储方式。

    C++实现示例：

    #include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 5; // 节点数（0~4）
    vector<vector<int>> adjList(n); // adjList[i]存储节点i的所有邻居
    
    // 添加边：0-1, 0-2, 1-3, 2-3, 3-4
    adjList[0].push_back(1);
    adjList[1].push_back(0); // 无向图，双向添加
    adjList[0].push_back(2);
    adjList[2].push_back(0);
    adjList[1].push_back(3);
    adjList[3].push_back(1);
    adjList[2].push_back(3);
    adjList[3].push_back(2);
    adjList[3].push_back(4);
    adjList[4].push_back(3);
    
    // 打印邻接表
    cout << "邻接表：" << endl;
    for (int i = 0; i < n; i++) {
        cout << "节点" << i << "的邻居：";
        for (int neighbor : adjList[i]) {
            cout << neighbor << " ";
        }
        cout << endl;
    }
    return 0;
}

    说明：后续算法实现均采用邻接表，因为其通用性更强。

    二、深度优先遍历（DFS）：“一条路走到底，不通再回头”

    1. 核心思想

    DFS的遍历逻辑类似“迷宫探索”：从起点出发，优先沿着一条路径走到最深层（无法再前进时），再回溯到上一个分叉路口，选择另一条未探索的路径，直到所有可达节点都被访问。

    可以用“栈”（Stack）或“递归”实现（递归本质是利用系统栈）：

    • 递归：代码简洁，适合理解，但节点数过多时可能栈溢出（C++默认栈大小较小，n>1e4需谨慎）。
    • 非递归（栈）：手动控制栈，避免栈溢出，适合大规模数据。

    2. 关键问题：避免重复访问

    由于图可能存在环（如节点0→1→2→0），若不标记已访问节点，会陷入无限循环。因此需额外维护一个visited数组（布尔型），visited[i] = true表示节点i已访问，false表示未访问。

    3. 递归实现DFS（推荐入门）

    步骤拆解

    1. 初始化visited数组，所有元素为false（未访问）。
    2. 定义递归函数dfs(int u)：
      • 标记当前节点u为已访问（visited[u] = true），并输出节点（或执行其他操作）。
      • 遍历节点u的所有邻居v：
        • 若v未访问（!visited[v]），则递归调用dfs(v)。
    3. 从起点（如节点0）调用dfs(0)，若图有多个连通分量（部分节点不可达），需遍历所有节点，对未访问的节点再次调用dfs。

    C++代码实现（无向图）

    #include <iostream>
#include <vector>
using namespace std;

// 全局变量：避免递归函数参数过多（也可封装为类成员）
vector<vector<int>> adjList; // 邻接表存储图
vector<bool> visited;        // 标记节点是否已访问

// 递归DFS函数：访问节点u及其所有可达节点
void dfs(int u) {
    // 1. 标记当前节点为已访问，并输出
    visited[u] = true;
    cout << u << " "; // 此处可替换为其他业务逻辑（如记录路径、计算距离等）
    
    // 2. 遍历当前节点的所有邻居
    for (int v : adjList[u]) {
        // 3. 若邻居未访问，则递归访问
        if (!visited[v]) {
            dfs(v);
        }
    }
}

int main() {
    int n, m; // n：节点数，m：边数
    cout << "请输入节点数n和边数m：";
    cin >> n >> m;
    
    // 初始化邻接表和visited数组
    adjList.resize(n);
    visited.resize(n, false);
    
    // 输入m条边（假设节点编号0~n-1）
    cout << "请输入" << m << "条边（格式：u v，代表u和v相连）：" << endl;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adjList[u].push_back(v);
        adjList[v].push_back(u); // 无向图，双向添加
    }
    
    // 执行DFS（从节点0开始）
    cout << "DFS遍历结果（从节点0出发）：";
    dfs(0);
    cout << endl;
    
    // （可选）处理非连通图：遍历所有节点，未访问则重新DFS
    cout << "DFS遍历结果（处理非连通图）：";
    fill(visited.begin(), visited.end(), false); // 重置visited
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i);
        }
    }
    cout << endl;
    
    return 0;
}

    运行示例

    请输入节点数n和边数m：5 5
请输入5条边（格式：u v，代表u和v相连）：
0 1
0 2
1 3
2 3
3 4
DFS遍历结果（从节点0出发）：0 1 3 2 4 
DFS遍历结果（处理非连通图）：0 1 3 2 4

    递归过程解析（以节点0为起点）

    1. dfs(0)：标记0为已访问，输出0；遍历邻居1、2。
    2. 先访问邻居1：dfs(1)，标记1，输出1；遍历邻居0（已访问）、3。
    3. 访问邻居3：dfs(3)，标记3，输出3；遍历邻居1（已访问）、2、4。
    4. 访问邻居2：dfs(2)，标记2，输出2；遍历邻居0（已访问）、3（已访问），回溯到3。
    5. 访问邻居4：dfs(4)，标记4，输出4；遍历邻居3（已访问），回溯到3→1→0。
    6. 0的邻居2已访问，遍历结束。

    4. 非递归实现DFS（栈）

    步骤拆解

    1. 初始化visited数组为false，创建一个栈（stack<int>）。
    2. 将起点u压入栈，标记为已访问（避免重复入栈），输出u。
    3. 当栈不为空时：
      • 取栈顶节点top（不弹出），遍历其所有邻居v。
      • 若找到未访问的邻居v：标记v为已访问，输出v，压入栈，跳出循环（继续深入）。
      • 若所有邻居均已访问：弹出栈顶节点（回溯）。

    C++代码实现

    #include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
    int n, m;
    cout << "请输入节点数n和边数m：";
    cin >> n >> m;
    
    vector<vector<int>> adjList(n);
    vector<bool> visited(n, false);
    
    // 输入边
    cout << "请输入" << m << "条边（格式：u v）：" << endl;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }
    
    // 非递归DFS（栈）
    stack<int> st;
    int start = 0; // 起点
    cout << "非递归DFS遍历结果（从节点" << start << "出发）：";
    
    // 起点入栈并标记
    st.push(start);
    visited[start] = true;
    cout << start << " ";
    
    while (!st.empty()) {
        int top = st.top();
        bool hasUnvisited = false; // 标记是否有未访问的邻居
        
        // 遍历栈顶节点的所有邻居
        for (int v : adjList[top]) {
            if (!visited[v]) {
                visited[v] = true;
                cout << v << " ";
                st.push(v);
                hasUnvisited = true;
                break; // 优先深入，跳出循环继续处理新入栈的节点
            }
        }
        
        // 若所有邻居已访问，弹出栈顶（回溯）
        if (!hasUnvisited) {
            st.pop();
        }
    }
    cout << endl;
    
    return 0;
}

    运行示例（与递归一致）

    请输入节点数n和边数m：5 5
请输入5条边（格式：u v）：
0 1
0 2
1 3
2 3
3 4
非递归DFS遍历结果（从节点0出发）：0 1 3 2 4

    三、广度优先遍历（BFS）：“一层一层扩散，先访问近处”

    1. 核心思想

    BFS的遍历逻辑类似“水波扩散”：从起点出发，先访问起点的所有邻居（第一层），再访问每个邻居的邻居（第二层），以此类推，按“距离起点的远近”逐层访问。

    BFS必须用“队列”（Queue）实现（队列的“先进先出”特性刚好匹配“逐层访问”的需求），无法用递归实现（递归是“先进后出”的栈逻辑）。

    2. 关键问题：避免重复访问

    与DFS相同，需维护visited数组，标记已访问的节点，避免因环导致的无限循环。

    3. BFS实现（队列）

    步骤拆解

    1. 初始化visited数组为false，创建一个队列（queue<int>）。
    2. 将起点u入队，标记为已访问，输出u。
    3. 当队列不为空时：
      • 出队队首节点front，遍历其所有邻居v。
      • 若v未访问：标记v为已访问，输出v，入队v。
    4. 重复步骤3，直到队列为空，所有可达节点均被访问。

    C++代码实现（无向图）

    #include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cout << "请输入节点数n和边数m：";
    cin >> n >> m;
    
    vector<vector<int>> adjList(n);
    vector<bool> visited(n, false);
    
    // 输入边
    cout << "请输入" << m << "条边（格式：u v）：" << endl;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }
    
    // BFS（队列）
    queue<int> q;
    int start = 0; // 起点
    cout << "BFS遍历结果（从节点" << start << "出发）：";
    
    // 起点入队并标记
    q.push(start);
    visited[start] = true;
    cout << start << " ";
    
    while (!q.empty()) {
        // 出队队首节点
        int front = q.front();
        q.pop();
        
        // 遍历队首节点的所有邻居
        for (int v : adjList[front]) {
            if (!visited[v]) {
                visited[v] = true;
                cout << v << " ";
                q.push(v); // 未访问的邻居入队，等待后续处理
            }
        }
    }
    cout << endl;
    
    // （可选）处理非连通图
    cout << "BFS遍历结果（处理非连通图）：";
    fill(visited.begin(), visited.end(), false);
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            q.push(i);
            visited[i] = true;
            cout << i << " ";
            while (!q.empty()) {
                int front = q.front();
                q.pop();
                for (int v : adjList[front]) {
                    if (!visited[v]) {
                        visited[v] = true;
                        cout << v << " ";
                        q.push(v);
                    }
                }
            }
        }
    }
    cout << endl;
    
    return 0;
}

    运行示例

    请输入节点数n和边数m：5 5
请输入5条边（格式：u v）：
0 1
0 2
1 3
2 3
3
    • @ 2025-8-22 20:14:08

      深度优先遍历（DFS）与广度优先遍历（BFS）教程

      一、核心概念与适用场景

      遍历方式 核心思想 适用场景 数据结构依赖
      深度优先遍历（DFS） 从起点出发，优先深入探索分支，直到无法前进再回溯，探索其他分支（“一条路走到黑，不通再回头”） 路径搜索、拓扑排序、连通性分析、迷宫求解、树的前/中/后序遍历 栈（手动实现）、递归（隐式栈）
      广度优先遍历（BFS） 从起点出发，优先遍历当前节点的所有邻接节点，再依次遍历邻接节点的邻接节点（“逐层扩散，不深探”） 最短路径（无权图）、层次遍历（树/图）、连通分量统计、朋友圈问题 队列（先进先出，FIFO）

      二、深度优先遍历（DFS）实现教程

      以“无向图”和“二叉树”为例，讲解两种常见实现方式。

      （一）无向图的DFS（递归实现）

      1. 图的存储（邻接表）

      先将图以“邻接表”形式存储，示例图节点为 0-1-2-3，边为 (0,1)、(0,2)、(1,3)、(2,3)，邻接表表示为：

      graph = [
    [1, 2],   # 节点0的邻接节点
    [0, 3],   # 节点1的邻接节点
    [0, 3],   # 节点2的邻接节点
    [1, 2]    # 节点3的邻接节点
]

      2. 递归实现步骤

      1. 初始化“访问标记数组”visited，记录节点是否已遍历，初始值全为 False。
      2. 定义递归函数：参数为“当前节点”，功能是标记节点为已访问→打印节点→遍历当前节点的所有邻接节点→若邻接节点未访问，递归调用自身。
      3. 从起点（如节点0）调用递归函数，若图有多个连通分量，需遍历所有未访问节点。

      3. 代码实现

      def dfs_recursion(graph, node, visited):
    visited[node] = True  # 标记已访问
    print(node, end=" ")  # 输出当前节点
    # 遍历邻接节点，未访问则递归
    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs_recursion(graph, neighbor, visited)

# 测试
graph = [[1,2],[0,3],[0,3],[1,2]]
visited = [False] * len(graph)
dfs_recursion(graph, 0, visited)  # 输出：0 1 3 2

      （二）无向图的DFS（栈实现，非递归）

      1. 实现步骤

      1. 初始化“访问标记数组”visited 和“栈”，将起点压入栈。
      2. 循环：栈不为空时，弹出栈顶节点→若未访问，标记为已访问并打印→将该节点的所有邻接节点（逆序压栈，保证遍历顺序与递归一致） 压入栈（已访问节点跳过）。

      2. 代码实现

      def dfs_stack(graph, start):
    visited = [False] * len(graph)
    stack = [start]  # 起点压栈
    while stack:
        node = stack.pop()  # 弹出栈顶
        if not visited[node]:
            visited[node] = True
            print(node, end=" ")
            # 邻接节点逆序压栈（确保遍历顺序）
            for neighbor in reversed(graph[node]):
                if not visited[neighbor]:
                    stack.append(neighbor)

# 测试
graph = [[1,2],[0,3],[0,3],[1,2]]
dfs_stack(graph, 0)  # 输出：0 1 3 2

      （三）二叉树的DFS（前/中/后序遍历）

      二叉树DFS的核心是“根节点的访问时机”，以如下二叉树为例：

          1
   / \
  2   3
 /
4

      1. 前序遍历（根→左→右）

      class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 递归实现
def preorder_dfs(root):
    if not root:
        return
    print(root.val, end=" ")  # 根
    preorder_dfs(root.left)   # 左
    preorder_dfs(root.right)  # 右

# 测试：构建二叉树并遍历
root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
preorder_dfs(root)  # 输出：1 2 4 3

      2. 中序遍历（左→根→右）、后序遍历（左→右→根）

      只需调整“根节点的打印顺序”，代码结构与前序一致，此处省略。

      三、广度优先遍历（BFS）实现教程

      以“无向图”和“二叉树层次遍历”为例，均基于队列实现。

      （一）无向图的BFS（队列实现）

      1. 实现步骤

      1. 初始化“访问标记数组”visited 和“队列”，将起点标记为已访问并加入队列。
      2. 循环：队列不为空时，弹出队首节点→打印节点→遍历该节点的所有邻接节点→若未访问，标记为已访问并加入队列。

      2. 代码实现

      from collections import deque  # 导入队列（高效）

def bfs_graph(graph, start):
    visited = [False] * len(graph)
    q = deque([start])  # 起点入队
    visited[start] = True
    while q:
        node = q.popleft()  # 弹出队首
        print(node, end=" ")
        # 邻接节点入队
        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                q.append(neighbor)

# 测试（同DFS示例图）
graph = [[1,2],[0,3],[0,3],[1,2]]
bfs_graph(graph, 0)  # 输出：0 1 2 3

      （二）二叉树的BFS（层次遍历）

      1. 实现步骤

      1. 初始化队列，若根节点非空，将根节点加入队列。
      2. 循环：队列不为空时，记录当前队列长度（即当前层节点数）→遍历当前层所有节点（弹出队首→打印→左子节点入队→右子节点入队）。

      2. 代码实现

      from collections import deque

def bfs_tree(root):
    if not root:
        return
    q = deque([root])
    while q:
        level_size = len(q)  # 当前层节点数
        for _ in range(level_size):
            node = q.popleft()
            print(node.val, end=" ")
            # 子节点入队
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)

# 测试（同DFS二叉树示例）
root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
bfs_tree(root)  # 输出：1 2 3 4（按层打印）

      四、关键区别与选择建议

      对比维度 DFS BFS
      空间复杂度 取决于最大递归深度/栈深度（最坏为 (O(n))，如链状图） 取决于最大层节点数（最坏为 (O(n))，如完全二叉树）
      时间复杂度 均为 (O(n + m))（(n) 为节点数，(m) 为边数）
      路径特性 不保证最短路径（无权图） 保证最短路径（无权图）
      适用场景 深探类问题（如找所有路径、拓扑排序） 层序/短路径类问题（如无权图最短路径、层次遍历）

      选择建议：

      • 若需找“无权图最短路径”或“按层处理节点”，选 BFS；
      • 若需“遍历所有可能路径”“深探分支”或“实现树的前/中/后序遍历”，选 DFS。
      • 1
      441
      已通过
      0
      题解被赞
      1. 关于
      2. 联系我们
      3. 隐私
      4. 服务条款
      5. 版权申诉
      6. Language
      7. 兼容模式
      8. 主题
      4. 在线咨询
      5. Worker 0, 36ms
      6. Powered by Hydro v4.13.3 Community