用邻接表和邻接矩阵实现图结构：C++实战代码详解（附DFS/BFS对比）

用邻接表和邻接矩阵实现图结构C实战代码详解附DFS/BFS对比在算法与数据结构的世界里图Graph无疑是最具表现力的结构之一。无论是社交网络中的好友关系还是城市间的交通路线甚至是编译器中的依赖分析图都能完美建模这些复杂关系。作为C开发者掌握图的两种经典实现方式——邻接表和邻接矩阵以及它们的核心遍历算法DFS和BFS是处理复杂关系数据的必备技能。本文将深入探讨这两种实现方式的代码细节分析它们在不同场景下的性能表现并通过完整的C示例展示如何在实际项目中应用这些知识。我们不仅会实现基础结构还会对比DFS和BFS在路径查找、环检测等实际场景中的差异帮助你在算法竞赛和工程开发中做出更明智的选择。1. 图的两种实现方式邻接表与邻接矩阵1.1 邻接表灵活的内存使用邻接表是图最常用的存储方式之一特别适合稀疏图边数远小于顶点数平方的图。它的核心思想是为每个顶点维护一个链表存储与之直接相连的顶点。// 使用vector和list实现邻接表 #include vector #include list class Graph { private: int V; // 顶点数 std::vectorstd::listint adj; // 邻接表 public: Graph(int vertices) : V(vertices), adj(vertices) {} void addEdge(int src, int dest) { adj[src].push_back(dest); // 如果是无向图需要添加反向边 // adj[dest].push_back(src); } const std::listint getNeighbors(int vertex) const { return adj[vertex]; } };邻接表的核心优势空间效率高只存储实际存在的边空间复杂度为O(VE)添加边快速O(1)时间复杂度遍历某顶点的邻接点高效O(degree(V))时间复杂度提示在C中使用vector代替list通常能获得更好的缓存局部性除非频繁在中间插入/删除元素。1.2 邻接矩阵快速的查询性能邻接矩阵使用二维数组表示图矩阵的行和列分别代表顶点矩阵值表示边是否存在或权重。// 邻接矩阵实现 #include vector class GraphMatrix { private: int V; std::vectorstd::vectorint matrix; public: GraphMatrix(int vertices) : V(vertices), matrix(vertices, std::vectorint(vertices, 0)) {} void addEdge(int src, int dest, int weight 1) { matrix[src][dest] weight; // 无向图需要对称设置 // matrix[dest][src] weight; } bool hasEdge(int src, int dest) const { return matrix[src][dest] ! 0; } int getWeight(int src, int dest) const { return matrix[src][dest]; } };邻接矩阵的典型特征查询边是否存在O(1)时间复杂度空间复杂度O(V²)适合稠密图添加/删除边O(1)时间复杂度遍历所有邻接点O(V)时间复杂度与边数无关1.3 实现方式对比与选择指南特性邻接表邻接矩阵空间复杂度O(V E)O(V²)添加边O(1)O(1)删除边O(degree(V))O(1)检查边是否存在O(degree(V))O(1)遍历邻接点O(degree(V))O(V)适用场景稀疏图、边遍历频繁的应用稠密图、频繁查询边的应用在实际项目中选择哪种实现取决于具体需求社交网络通常选择邻接表因为用户好友关系是典型的稀疏图交通网络城市间直飞航线较少邻接表更合适图像处理像素邻接关系密集邻接矩阵可能更好2. 深度优先搜索(DFS)实现与优化2.1 递归实现简洁直观DFS遵循一条路走到黑的策略尽可能深地探索图的分支。void DFS_recursive(const Graph g, int v, std::vectorbool visited) { visited[v] true; std::cout v ; for (int neighbor : g.getNeighbors(v)) { if (!visited[neighbor]) { DFS_recursive(g, neighbor, visited); } } }递归DFS的特点代码简洁直接反映算法逻辑隐式使用调用栈可能面临栈溢出风险深度超过几千层2.2 迭代实现避免栈溢出使用显式栈的迭代实现能避免递归深度限制。#include stack void DFS_iterative(const Graph g, int start) { std::vectorbool visited(g.vertexCount(), false); std::stackint s; s.push(start); while (!s.empty()) { int v s.top(); s.pop(); if (!visited[v]) { visited[v] true; std::cout v ; // 注意邻接点入栈顺序会影响遍历顺序 for (auto it g.getNeighbors(v).rbegin(); it ! g.getNeighbors(v).rend(); it) { if (!visited[*it]) { s.push(*it); } } } } }注意迭代实现中邻接点入栈顺序与递归版不同会导致遍历顺序差异但不影响DFS性质。2.3 DFS应用场景拓扑排序有向无环图的线性排序void topologicalSortUtil(int v, std::vectorbool visited, std::stackint stack, const Graph g) { visited[v] true; for (int neighbor : g.getNeighbors(v)) { if (!visited[neighbor]) { topologicalSortUtil(neighbor, visited, stack, g); } } stack.push(v); }连通分量检测查找图中所有连通区域void findConnectedComponents(const Graph g) { std::vectorbool visited(g.vertexCount(), false); for (int v 0; v g.vertexCount(); v) { if (!visited[v]) { DFS_recursive(g, v, visited); std::cout \n--- New Component ---\n; } } }环路检测判断有向图是否包含环bool isCyclicUtil(int v, std::vectorbool visited, std::vectorbool recStack, const Graph g) { if (!visited[v]) { visited[v] true; recStack[v] true; for (int neighbor : g.getNeighbors(v)) { if (!visited[neighbor] isCyclicUtil(neighbor, visited, recStack, g)) { return true; } else if (recStack[neighbor]) { return true; } } } recStack[v] false; return false; }3. 广度优先搜索(BFS)实现与优化3.1 标准BFS实现BFS使用队列实现层层推进的遍历策略天然适合寻找最短路径。#include queue void BFS(const Graph g, int start) { std::vectorbool visited(g.vertexCount(), false); std::queueint q; q.push(start); visited[start] true; while (!q.empty()) { int v q.front(); q.pop(); std::cout v ; for (int neighbor : g.getNeighbors(v)) { if (!visited[neighbor]) { visited[neighbor] true; q.push(neighbor); } } } }BFS的关键特性使用队列保证先进先出的访问顺序非递归实现无栈溢出风险首次访问时即找到最短路径无权图3.2 BFS应用场景最短路径查找无权图std::vectorint shortestPaths(const Graph g, int start) { std::vectorint distances(g.vertexCount(), -1); std::queueint q; q.push(start); distances[start] 0; while (!q.empty()) { int v q.front(); q.pop(); for (int neighbor : g.getNeighbors(v)) { if (distances[neighbor] -1) { distances[neighbor] distances[v] 1; q.push(neighbor); } } } return distances; }网络爬虫层级抓取按距离分批抓取网页void crawlWeb(const Graph webGraph, int startPage) { std::vectorbool visited(webGraph.vertexCount(), false); std::queuestd::pairint, int q; // page, level q.push({startPage, 0}); visited[startPage] true; while (!q.empty()) { auto current q.front(); q.pop(); std::cout Crawling page current.first at level current.second \n; if (current.second 3) { // 限制抓取深度 for (int neighbor : webGraph.getNeighbors(current.first)) { if (!visited[neighbor]) { visited[neighbor] true; q.push({neighbor, current.second 1}); } } } } }社交网络好友推荐寻找二度、三度好友void recommendFriends(const Graph socialGraph, int user, int maxDegree) { std::vectorbool visited(socialGraph.vertexCount(), false); std::queuestd::pairint, int q; // user, degree q.push({user, 0}); visited[user] true; while (!q.empty()) { auto current q.front(); q.pop(); if (current.second 0 current.second maxDegree) { std::cout Recommended friend: current.first (degree current.second )\n; } if (current.second maxDegree) { for (int neighbor : socialGraph.getNeighbors(current.first)) { if (!visited[neighbor]) { visited[neighbor] true; q.push({neighbor, current.second 1}); } } } } }4. DFS与BFS的对比与实战选择4.1 算法特性对比特性DFSBFS数据结构栈显式或隐式队列空间复杂度O(h)h为最大深度O(w)w为最大宽度最短路径不保证无权图保证无权图适用场景拓扑排序、连通分量、环路最短路径、层级遍历实现复杂度递归简单迭代稍复杂统一使用队列较简单内存消耗通常较少除非图很深可能较大图很宽时4.2 实际应用选择指南路径查找需要最短路径 → BFS需要所有可能路径 → DFS带权图 → Dijkstra或A*算法图结构分析检测环路 → DFS连通分量 → DFS或BFS拓扑排序 → DFS性能考量图又宽又浅 → BFS可能更快图又窄又深 → DFS可能更省内存已知目标顶点距离近 → BFS目标可能在深层 → DFS4.3 性能优化技巧双向BFS当起点和终点都已知时从两端同时进行BFS相遇时即找到路径。int bidirectionalBFS(const Graph g, int start, int target) { std::vectorbool visitedFromStart(g.vertexCount(), false); std::vectorbool visitedFromTarget(g.vertexCount(), false); std::queueint qStart, qTarget; qStart.push(start); visitedFromStart[start] true; qTarget.push(target); visitedFromTarget[target] true; while (!qStart.empty() !qTarget.empty()) { // 从起点端扩展 int size qStart.size(); for (int i 0; i size; i) { int v qStart.front(); qStart.pop(); if (visitedFromTarget[v]) { return ...; // 计算合并路径长度 } for (int neighbor : g.getNeighbors(v)) { if (!visitedFromStart[neighbor]) { visitedFromStart[neighbor] true; qStart.push(neighbor); } } } // 从终点端扩展类似代码 // ... } return -1; // 无连接 }迭代加深DFS结合DFS空间效率和BFS完备性的混合算法。bool DLS(const Graph g, int v, int target, int limit) { if (v target) return true; if (limit 0) return false; for (int neighbor : g.getNeighbors(v)) { if (DLS(g, neighbor, target, limit - 1)) { return true; } } return false; } bool IDDFS(const Graph g, int start, int target, int max_depth) { for (int depth 0; depth max_depth; depth) { if (DLS(g, start, target, depth)) { return true; } } return false; }并行化搜索对于大型图可以考虑并行化DFS或BFS。对BFS可以并行处理同一层的多个节点对DFS可以并行探索不同的分支在真实项目中使用这些算法时我通常会根据图的大小和特性先进行小规模测试。比如在社交网络分析中当需要查找用户间的潜在联系时BFS通常是首选而在处理依赖关系解析时DFS的拓扑排序能力则更为关键。