C++图的遍历算法详解（从零开始掌握深度优先与广度优先搜索）

什么是图？

图由顶点（Vertex）和边（Edge）组成。顶点代表对象，边表示对象之间的关系。图可以是有向的（箭头表示方向）或无向的（双向连接）。

在C++中，我们通常用以下两种方式表示图：

• 邻接矩阵（Adjacency Matrix）：用二维数组表示，适合稠密图。
• 邻接表（Adjacency List）：用链表或vector数组表示，适合稀疏图，更节省空间。

本教程采用邻接表实现，因为它更常用且高效。

1. 深度优先搜索（DFS）

深度优先搜索（DFS）的核心思想是：从一个起点出发，沿着一条路径尽可能深入，直到无法继续为止，然后回溯并尝试其他路径。它类似于“走迷宫”时一直往前走，走到死胡同再返回。

DFS通常使用递归或栈来实现。下面我们用递归方式实现。

C++ DFS代码示例

#include <iostream>#include <vector>#include <cstring> // for memsetusing namespace std;const int MAXN = 1000; // 最大顶点数vector<int> graph[MAXN]; // 邻接表bool visited[MAXN];      // 访问标记数组// DFS递归函数void dfs(int node) {    visited[node] = true;    cout << node << " ";    // 遍历所有相邻顶点    for (int neighbor : graph[node]) {        if (!visited[neighbor]) {            dfs(neighbor);        }    }}int main() {    // 构建图：例如 0->1, 0->2, 1->3, 2->3    graph[0].push_back(1);    graph[0].push_back(2);    graph[1].push_back(3);    graph[2].push_back(3);    memset(visited, false, sizeof(visited));    cout << "DFS遍历顺序: ";    dfs(0); // 从顶点0开始    cout << endl;    return 0;}

运行结果可能是：0 1 3 2（具体顺序取决于邻接表中邻居的存储顺序）。

2. 广度优先搜索（BFS）

广度优先搜索（BFS）则是“一层一层”地遍历图。它从起点开始，先访问所有直接相连的邻居，再访问邻居的邻居，依此类推。BFS常用于求最短路径（在无权图中）。

BFS必须使用队列（Queue）来实现，确保先进先出（FIFO）。

C++ BFS代码示例

#include <iostream>#include <vector>#include <queue>#include <cstring>using namespace std;const int MAXN = 1000;vector<int> graph[MAXN];bool visited[MAXN];void bfs(int start) {    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() {    // 同样的图结构    graph[0].push_back(1);    graph[0].push_back(2);    graph[1].push_back(3);    graph[2].push_back(3);    memset(visited, false, sizeof(visited));    cout << "BFS遍历顺序: ";    bfs(0);    cout << endl;    return 0;}

运行结果通常是：0 1 2 3，体现了“层级遍历”的特点。

DFS vs BFS 对比

总结

通过本教程，你已经掌握了C++图的遍历两大核心算法：深度优先搜索C++实现和广度优先搜索C++实现。它们是解决更复杂图算法教程问题（如最短路径、最小生成树等）的基础。

建议你动手敲一遍代码，修改图的结构，观察输出变化，加深理解。记住：编程不是看会的，而是练会的！

如果你觉得本文对你有帮助，欢迎分享给更多正在学习图算法教程的朋友！