C++图的遍历算法详解（深度优先与广度优先搜索完整实现）

什么是图？

图（Graph）是由顶点（Vertex）和边（Edge）组成的数据结构。顶点代表对象，边代表对象之间的关系。图可以是有向的（如网页链接），也可以是无向的（如朋友关系）。

在C++中，我们通常用邻接表（Adjacency List）来表示图，因为它节省空间且便于遍历。

1. 深度优先搜索（DFS）

深度优先搜索（DFS）就像走迷宫：一条路走到黑，直到走不通才回退。它使用递归或栈来实现。

DFS 的 C++ 实现

#include <iostream>#include <vector>#include <stack>using namespace std;// 使用邻接表表示图class Graph {private:    int V; // 顶点数量    vector<vector<int>> adj; // 邻接表public:    Graph(int vertices) {        V = vertices;        adj.resize(V);    }    void addEdge(int u, int v) {        adj[u].push_back(v); // 无向图则需双向添加    }    // 递归版 DFS    void DFSUtil(int v, vector<bool>& visited) {        visited[v] = true;        cout << v << " ";        for (int neighbor : adj[v]) {            if (!visited[neighbor]) {                DFSUtil(neighbor, visited);            }        }    }    void DFS(int start) {        vector<bool> visited(V, false);        DFSUtil(start, visited);        cout << endl;    }};int main() {    Graph g(5);    g.addEdge(0, 1);    g.addEdge(0, 2);    g.addEdge(1, 3);    g.addEdge(2, 4);    cout << "DFS 遍历结果（从顶点 0 开始）: ";    g.DFS(0);    return 0;}

这段代码展示了如何用递归实现 深度优先搜索C++。程序会输出：0 1 3 2 4。

2. 广度优先搜索（BFS）

广度优先搜索（BFS）则像水波扩散：先访问所有直接邻居，再访问邻居的邻居。它使用队列（Queue）实现。

BFS 的 C++ 实现

#include <iostream>#include <vector>#include <queue>using namespace std;class Graph {private:    int V;    vector<vector<int>> adj;public:    Graph(int vertices) {        V = vertices;        adj.resize(V);    }    void addEdge(int u, int v) {        adj[u].push_back(v);    }    void BFS(int start) {        vector<bool> visited(V, false);        queue<int> q;        visited[start] = true;        q.push(start);        while (!q.empty()) {            int v = q.front();            cout << v << " ";            q.pop();            for (int neighbor : adj[v]) {                if (!visited[neighbor]) {                    visited[neighbor] = true;                    q.push(neighbor);                }            }        }        cout << endl;    }};int main() {    Graph g(5);    g.addEdge(0, 1);    g.addEdge(0, 2);    g.addEdge(1, 3);    g.addEdge(2, 4);    cout << "BFS 遍历结果（从顶点 0 开始）: ";    g.BFS(0);    return 0;}

运行后输出：0 1 2 3 4。这正是 广度优先搜索C++ 的典型遍历顺序。

DFS 与 BFS 对比

• 空间复杂度：DFS 使用递归栈，最坏 O(V)；BFS 使用队列，最坏也是 O(V)。
• 应用场景：DFS 适合找路径、拓扑排序；BFS 适合找最短路径（无权图）。
• 实现难度：两者都简单，但 DFS 更容易用递归写出。

总结

通过本文，你已经掌握了 C++图的遍历 的两种核心方法。无论是 深度优先搜索C++ 还是 广度优先搜索C++，都是解决实际问题的利器。建议你动手敲一遍代码，加深理解。后续可以尝试扩展为有向图、带权图，甚至解决 LeetCode 上的相关题目！

记住：图算法实现的关键在于理解数据结构与遍历逻辑。多练习，你也能成为算法高手！