用邻接表和邻接矩阵实现图结构：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::vector<std::list<int>> 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::list<int>& getNeighbors(int vertex) const { return adj[vertex]; } };邻接表的核心优势：
- 空间效率高：只存储实际存在的边，空间复杂度为O(V+E)
- 添加边快速：O(1)时间复杂度
- 遍历某顶点的邻接点高效：O(degree(V))时间复杂度
提示：在C++中，使用vector代替list通常能获得更好的缓存局部性，除非频繁在中间插入/删除元素。
1.2 邻接矩阵：快速的查询性能
邻接矩阵使用二维数组表示图，矩阵的行和列分别代表顶点，矩阵值表示边是否存在（或权重）。
// 邻接矩阵实现 #include <vector> class GraphMatrix { private: int V; std::vector<std::vector<int>> matrix; public: GraphMatrix(int vertices) : V(vertices), matrix(vertices, std::vector<int>(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::vector<bool>& 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::vector<bool> visited(g.vertexCount(), false); std::stack<int> 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::vector<bool>& visited, std::stack<int>& 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::vector<bool> 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::vector<bool>& visited, std::vector<bool>& 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::vector<bool> visited(g.vertexCount(), false); std::queue<int> 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::vector<int> shortestPaths(const Graph& g, int start) { std::vector<int> distances(g.vertexCount(), -1); std::queue<int> 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::vector<bool> visited(webGraph.vertexCount(), false); std::queue<std::pair<int, 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::vector<bool> visited(socialGraph.vertexCount(), false); std::queue<std::pair<int, 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 算法特性对比
| 特性 | DFS | BFS |
|---|---|---|
| 数据结构 | 栈（显式或隐式） | 队列 |
| 空间复杂度 | O(h)（h为最大深度） | O(w)（w为最大宽度） |
| 最短路径 | 不保证（无权图） | 保证（无权图） |
| 适用场景 | 拓扑排序、连通分量、环路 | 最短路径、层级遍历 |
| 实现复杂度 | 递归简单，迭代稍复杂 | 统一使用队列较简单 |
| 内存消耗 | 通常较少（除非图很深） | 可能较大（图很宽时） |
4.2 实际应用选择指南
路径查找：
- 需要最短路径 → BFS
- 需要所有可能路径 → DFS
- 带权图 → Dijkstra或A*算法
图结构分析：
- 检测环路 → DFS
- 连通分量 → DFS或BFS
- 拓扑排序 → DFS
性能考量：
- 图又宽又浅 → BFS可能更快
- 图又窄又深 → DFS可能更省内存
- 已知目标顶点距离近 → BFS
- 目标可能在深层 → DFS
4.3 性能优化技巧
双向BFS：当起点和终点都已知时，从两端同时进行BFS，相遇时即找到路径。
int bidirectionalBFS(const Graph& g, int start, int target) { std::vector<bool> visitedFromStart(g.vertexCount(), false); std::vector<bool> visitedFromTarget(g.vertexCount(), false); std::queue<int> 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的拓扑排序能力则更为关键。
