专栏文章

C++图遍历详解（已完结）

EEmily1234
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min1b0gp
此快照首次捕获于
2025/12/01 18:56
3 个月前
此快照最后确认于
2025/12/01 18:56
3 个月前
查看原文
在 C++ 中，图的遍历是指从图中的某一顶点出发，按照一定的规则访问图中所有顶点的过程，核心分为 ** 深度优先搜索（DFS，Depth-First Search）和广度优先搜索（BFS，Breadth-First Search）** 两种方式。本文将从图的存储结构入手，详细讲解两种遍历算法的原理、实现及应用场景。

一、图的存储结构

图的遍历依赖于其存储方式，C++ 中常用的存储结构有邻接矩阵和邻接表，二者各有优劣：
  1. 邻接矩阵：用二维数组表示顶点间的邻接关系，适用于稠密图。
    • 优点：访问两点间的邻接关系时间复杂度为 O (1)。
    • 缺点：空间复杂度为 O (n²)（n 为顶点数），稀疏图会浪费大量空间。
  2. 邻接表：用数组 + 链表（或 vector）表示，适用于稀疏图。
  • 优点：空间复杂度为 O (n+e)（e 为边数），节省空间。
  • 缺点：访问两点间的邻接关系需要遍历链表，时间复杂度为 O (k)（k 为顶点的度）。
示例存储实现：
CPP
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

// 邻接表存储图（推荐，稀疏图高效）
class Graph {
public:
    int n; // 顶点数
    vector<vector<int>> adj; // 邻接表：adj[u]存储u的邻接顶点

    Graph(int num) : n(num), adj(num) {}

    // 添加无向边u-v
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u); // 有向图则删除此行
    }
};

// 邻接矩阵存储图（稠密图适用）
class GraphMatrix {
public:
    int n;
    vector<vector<int>> mat; // mat[u][v]=1表示u和v邻接，0表示不邻接

    GraphMatrix(int num) : n(num), mat(num, vector<int>(num, 0)) {}

    void addEdge(int u, int v) {
        mat[u][v] = 1;
        mat[v][u] = 1; // 有向图则删除此行
    }
};

二、深度优先搜索（DFS）

1. 算法原理

深度优先搜索遵循 “先深后广” 的原则：从起始顶点出发，访问该顶点后，递归地访问其未被访问的邻接顶点，直到无法继续深入，再回溯到上一个顶点，继续访问其他未被访问的邻接顶点。 可以类比为 “走迷宫”：遇到岔路选一条一直走到底，走不通就回头换另一条。

2. 实现方式

DFS 的实现有递归版（简洁，利用函数调用栈）和非递归版（手动用栈模拟递归）两种，核心是维护一个访问标记数组，避免重复访问顶点。
  • CPP
    递归版 DFS（邻接表）
CPP
// 递归版DFS：从顶点u开始遍历
void dfsRecursive(const Graph& g, int u, vector<bool>& visited) {
    visited[u] = true; // 标记为已访问
    cout << u << " ";  // 访问顶点（可替换为其他操作）

    // 遍历u的所有邻接顶点
    for (int v : g.adj[u]) {
        if (!visited[v]) { // 未访问则递归
            dfsRecursive(g, v, visited);
        }
    }
}
  • CPP
    非递归版 DFS（邻接表，栈模拟）
CPP
  
// 非递归版DFS：从顶点u开始遍历
void dfsIterative(const Graph& g, int u, vector<bool>& visited) {
    stack<int> st;
    st.push(u);
    visited[u] = true;
    cout << u << " ";

    while (!st.empty()) {
        int cur = st.top();
        bool hasUnvisited = false;

        // 查找当前顶点的未访问邻接顶点
        for (int v : g.adj[cur]) {
            if (!visited[v]) {
                visited[v] = true;
                cout << v << " ";
                st.push(v);
                hasUnvisited = true;
                break; // 深度优先，找到一个就入栈
            }
        }

        // 无未访问邻接顶点，出栈（回溯）
        if (!hasUnvisited) {
            st.pop();
        }
    }
}

3. 时间复杂度

  • 邻接表：O (n+e)，需遍历所有顶点和边。
  • 邻接矩阵：O (n²)，需遍历每个顶点的所有可能邻接顶点。

三、广度优先搜索（BFS）

1. 算法原理

广度优先搜索遵循 “先广后深” 的原则：从起始顶点出发，先访问该顶点的所有邻接顶点，再依次访问每个邻接顶点的邻接顶点，逐层扩散。 可以类比为 “水滴扩散”：从起点开始，先覆盖第一层邻接顶点，再覆盖第二层，以此类推。

2. 实现方式

BFS 的核心是使用队列存储待访问的顶点，同样需要访问标记数组避免重复访问，无递归版（队列是天然的实现方式）。
BFS 实现（邻接表，队列）
CPP
// BFS：从顶点u开始遍历
void bfs(const Graph& g, int u, vector<bool>& visited) {
    queue<int> q;
    visited[u] = true;
    q.push(u);
    cout << u << " ";

    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        // 遍历当前顶点的所有邻接顶点
        for (int v : g.adj[cur]) {
            if (!visited[v]) {
                visited[v] = true;
                cout << v << " ";
                q.push(v); // 入队待访问
            }
        }
    }
}

3. 时间复杂度

与 DFS 相同：
  • 邻接表：O (n+e)。
  • 邻接矩阵：O (n²)。

四、完整测试示例

结合上述实现，编写完整的图遍历测试代码：
CPP
int main() {
    // 构建图：顶点0-4，边为0-1,0-2,1-3,1-4,2-4
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 4);

    vector<bool> visited(g.n, false);
    cout << "递归版DFS遍历结果：";
    dfsRecursive(g, 0, visited); // 从顶点0开始
    cout << endl;

    fill(visited.begin(), visited.end(), false);
    cout << "非递归版DFS遍历结果：";
    dfsIterative(g, 0, visited);
    cout << endl;

    fill(visited.begin(), visited.end(), false);
    cout << "BFS遍历结果：";
    bfs(g, 0, visited);
    cout << endl;

    return 0;
}
输出结果：
CPP
递归版DFS遍历结果：0 1 3 4 2 
非递归版DFS遍历结果：0 1 3 4 2 
BFS遍历结果：0 1 2 3 4

五、处理非连通图

上述示例是连通图，若为非连通图，需遍历所有顶点，对未访问的顶点重新启动遍历：
CPP
// 遍历非连通图（以递归DFS为例）
void traverseDisconnectedGraph(const Graph& g) {
    vector<bool> visited(g.n, false);
    cout << "非连通图的DFS遍历结果：";
    for (int i = 0; i < g.n; ++i) {
        if (!visited[i]) {
            dfsRecursive(g, i, visited);
        }
    }
    cout << endl;
}

六、应用场景

  1. DFS：
  • 路径查找（如迷宫求解、哈密顿路径）。
  • 拓扑排序（有向无环图）。
  • 连通分量查找、割点 / 桥检测。
  • 回溯法（如排列组合、子集问题）。
  1. BFS：
  • 最短路径（无权图的单源最短路径）。
  • 层次遍历（如树的层序遍历、图的分层扩散）。
  • 广域搜索（如社交网络的好友推荐）。
  • 连通分量的层次划分。

七、关键注意事项

  • 访问标记：必须使用visited数组标记已访问顶点，避免循环访问（如环图）。
  • 存储结构选择：稀疏图用邻接表，稠密图用邻接矩阵。
  • 递归深度限制：递归版 DFS 在顶点数过多时可能触发栈溢出，需改用非递归版。
  • 有向图处理：添加边时仅需adj[u].push_back(v)，遍历逻辑与无向图一致，但需注意边的方向性。

八、刷题

P10109 [GESP202312 六级] 工作沟通
P10722 [GESP202406 六级] 二叉树

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...