C++实战：用邻接表实现图的深度优先遍历（附完整代码）
当你第一次接触图论算法时，可能会被各种抽象概念弄得晕头转向。但作为C++开发者，没有什么比直接动手实现一个算法更能加深理解的了。今天我们就来彻底搞懂如何用邻接表表示图结构，并实现深度优先遍历(DFS)算法——这个在路径查找、拓扑排序等领域广泛应用的基础算法。
邻接表相比邻接矩阵，在稀疏图中能显著节省内存空间。想象一下社交网络中的好友关系：每个人（顶点）的好友列表（邻接表）通常不会太多，这时用邻接表就再合适不过了。下面我们将从零开始，一步步构建完整的解决方案。
1. 图的邻接表表示
在C++中，我们通常用vector容器数组来实现邻接表。这种结构既保留了动态扩展的灵活性，又能通过索引快速访问任意顶点的邻居。
#include <vector> using namespace std; const int MAX_VERTICES = 1000; // 预设最大顶点数 vector<int> adjList[MAX_VERTICES]; // 邻接表数组邻接表的核心思想很简单：数组的每个元素对应图的一个顶点，存储该顶点的所有邻接顶点。例如adjList[0]包含顶点0的所有邻居。
构建邻接表的典型流程：
- 读取顶点数V和边数E
- 逐条读取边信息，填充邻接表
- （可选）对每个顶点的邻居列表排序，确保遍历顺序一致
int V, E; cin >> V >> E; for(int i = 0; i < E; ++i) { int u, v; cin >> u >> v; adjList[u].push_back(v); // 如果是无向图，还需要添加反向边 // adjList[v].push_back(u); } // 对邻接表排序以确保遍历顺序一致 for(int i = 0; i < V; ++i) { sort(adjList[i].begin(), adjList[i].end()); }2. 深度优先遍历原理与实现
深度优先遍历就像走迷宫时始终坚持"右手法则"——遇到岔路就选择一条路走到底，直到无路可走再回溯。这种策略天然适合用递归实现。
DFS算法的三个关键点：
- 访问标记数组（避免重复访问）
- 递归探索未访问的邻居
- 回溯机制
bool visited[MAX_VERTICES] = {false}; // 访问标记数组 void dfs(int current) { visited[current] = true; cout << current << " "; // 处理当前顶点（这里简单打印） for(int neighbor : adjList[current]) { if(!visited[neighbor]) { dfs(neighbor); // 递归访问未探索的邻居 } } }注意：对于非连通图，需要从每个未访问的顶点启动DFS，确保遍历整个图。
3. 完整实现与边界处理
一个健壮的DFS实现需要考虑多种边界情况：空图、孤立顶点、自环边等。下面是完整实现：
#include <iostream> #include <vector> #include <algorithm> using namespace std; const int MAX_V = 1000; vector<int> adj[MAX_V]; bool vis[MAX_V] = {false}; void dfs(int u) { vis[u] = true; cout << u << " "; for(int v : adj[u]) { if(!vis[v]) { dfs(v); } } } void dfsAll(int V) { fill(vis, vis + V, false); // 重置访问标记 for(int i = 0; i < V; ++i) { if(!vis[i]) { dfs(i); } } } int main() { int V, E; cin >> V >> E; // 构建邻接表 for(int i = 0; i < E; ++i) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); // 无向图需要双向添加 } // 排序确保遍历顺序一致 for(int i = 0; i < V; ++i) { sort(adj[i].begin(), adj[i].end()); } // 执行DFS遍历 dfsAll(V); return 0; }时间复杂度分析：
- 邻接表构建：O(V + E)
- DFS遍历：O(V + E)
- 空间复杂度：O(V)（主要来自递归栈和访问数组）
4. 实战应用与变体
掌握了基础DFS后，我们可以轻松扩展出许多实用功能：
1. 路径记录
vector<int> path; void dfsWithPath(int u, int target) { path.push_back(u); if(u == target) { // 找到目标，处理路径 for(int node : path) cout << node << " "; return; } for(int v : adj[u]) { if(!vis[v]) { vis[v] = true; dfsWithPath(v, target); vis[v] = false; // 回溯 } } path.pop_back(); // 回溯 }2. 连通分量计数
int countComponents(int V) { int count = 0; fill(vis, vis + V, false); for(int i = 0; i < V; ++i) { if(!vis[i]) { dfs(i); ++count; } } return count; }3. 拓扑排序（有向无环图）
vector<int> topoOrder; void topologicalSort(int u) { vis[u] = true; for(int v : adj[u]) { if(!vis[v]) { topologicalSort(v); } } topoOrder.push_back(u); // 后序添加 }5. 性能优化与常见陷阱
优化技巧：
- 使用迭代代替递归避免栈溢出
- 对大型图考虑并行DFS
- 使用位运算压缩访问标记数组
常见错误：
- 忘记重置访问标记数组
- 混淆有向图和无向图的边添加方式
- 忽略非连通图的情况
- 递归深度过大导致栈溢出
// 迭代版DFS示例（使用栈） void dfsIterative(int start) { stack<int> s; s.push(start); vis[start] = true; while(!s.empty()) { int u = s.top(); s.pop(); cout << u << " "; // 注意压栈顺序要与递归顺序一致 for(auto it = adj[u].rbegin(); it != adj[u].rend(); ++it) { int v = *it; if(!vis[v]) { vis[v] = true; s.push(v); } } } }在实际项目中，我经常遇到需要调整DFS遍历顺序的情况。比如在处理依赖关系时，逆后序的DFS结果直接就是拓扑排序。而调试DFS最有效的方法，就是在关键节点打印状态信息，配合小规模测试用例逐步验证。
