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

Emily1234 · 2025-11-24 20:26:09 · 算法·理论

在 C++ 中，图的遍历是指从图中的某一顶点出发，按照一定的规则访问图中所有顶点的过程，核心分为 深度优先搜索（DFS，Depth-First Search）和广度优先搜索（BFS，Breadth-First Search） 两种方式。本文将从图的存储结构入手，详细讲解两种遍历算法的原理、实现及应用场景。

一、图的存储结构

图的遍历依赖于其存储方式，C++ 中常用的存储结构有邻接矩阵和邻接表，二者各有优劣：

邻接矩阵：用二维数组表示顶点间的邻接关系，适用于稠密图。
- 优点：访问两点间的邻接关系时间复杂度为 O (1)。
- 缺点：空间复杂度为 O (n²)（n 为顶点数），稀疏图会浪费大量空间。
邻接表：用数组 + 链表（或 vector）表示，适用于稀疏图。
- 优点：空间复杂度为 O (n+e)（e 为边数），节省空间。
- 缺点：访问两点间的邻接关系需要遍历链表，时间复杂度为 O (k)（k 为顶点的度）。

示例存储实现：

#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 的实现有递归版（简洁，利用函数调用栈）和非递归版（手动用栈模拟递归）两种，核心是维护一个访问标记数组，避免重复访问顶点。

递归版 DFS（邻接表）

// 递归版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);
    }
}
}

非递归版 DFS（邻接表，栈模拟）

// 非递归版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²)。

四、完整测试示例

结合上述实现，编写完整的图遍历测试代码：

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;
}

输出结果：

递归版DFS遍历结果：0 1 3 4 2 
非递归版DFS遍历结果：0 1 3 4 2 
BFS遍历结果：0 1 2 3 4

五、处理非连通图

上述示例是连通图，若为非连通图，需遍历所有顶点，对未访问的顶点重新启动遍历：

// 遍历非连通图（以递归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;
}

六、应用场景

DFS：

路径查找（如迷宫求解、哈密顿路径）。
拓扑排序（有向无环图）。
连通分量查找、割点 / 桥检测。
回溯法（如排列组合、子集问题）。
1. BFS：
最短路径（无权图的单源最短路径）。
层次遍历（如树的层序遍历、图的分层扩散）。
广域搜索（如社交网络的好友推荐）。
连通分量的层次划分。
七、关键注意事项
访问标记：必须使用visited数组标记已访问顶点，避免循环访问（如环图）。
存储结构选择：稀疏图用邻接表，稠密图用邻接矩阵。
递归深度限制：递归版 DFS 在顶点数过多时可能触发栈溢出，需改用非递归版。
有向图处理：添加边时仅需adj[u].push_back(v)，遍历逻辑与无向图一致，但需注意边的方向性。
八、刷题

P10109 [GESP202312 六级] 工作沟通

P10722 [GESP202406 六级] 二叉树