C++实战：用邻接表实现图的深度优先遍历（附完整代码）

C实战用邻接表实现图的深度优先遍历附完整代码当你第一次接触图论算法时可能会被各种抽象概念弄得晕头转向。但作为C开发者没有什么比直接动手实现一个算法更能加深理解的了。今天我们就来彻底搞懂如何用邻接表表示图结构并实现深度优先遍历(DFS)算法——这个在路径查找、拓扑排序等领域广泛应用的基础算法。邻接表相比邻接矩阵在稀疏图中能显著节省内存空间。想象一下社交网络中的好友关系每个人顶点的好友列表邻接表通常不会太多这时用邻接表就再合适不过了。下面我们将从零开始一步步构建完整的解决方案。1. 图的邻接表表示在C中我们通常用vector容器数组来实现邻接表。这种结构既保留了动态扩展的灵活性又能通过索引快速访问任意顶点的邻居。#include vector using namespace std; const int MAX_VERTICES 1000; // 预设最大顶点数 vectorint 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; vectorint 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. 路径记录vectorint 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. 拓扑排序有向无环图vectorint 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) { stackint 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最有效的方法就是在关键节点打印状态信息配合小规模测试用例逐步验证。