C++数据结构进阶｜图（Graph）详解：从存储到面试高频算法实战

前言

在C++数据结构进阶体系中，图（Graph）是最具通用性、也最考验综合能力的结构——它不像堆、并查集那样有固定的操作模板，而是灵活适配多种复杂场景，涵盖“存储、遍历、最短路径、拓扑排序”等核心考点，是面试中区分基础与进阶水平的关键题型。

本文专为C++学习者、面试备考者打造，全程贴合笔试面试场景，延续前序并查集博客的风格，从“为什么需要图”出发，拆解图的核心概念、两种主流存储方式、必备遍历算法，再到面试高频真题解析，帮你从“懂概念”到“能编码、会应用”，彻底吃透图的进阶知识点。

适合人群：已掌握C++基础（vector、链表、队列、栈）、了解堆、并查集等进阶结构，想要攻克图的存储与算法，应对面试中图相关考题的学习者；需要解决路径规划、拓扑排序等实际问题的开发者。

一、为什么需要图？—— 打破线性与树形的局限

我们之前学过的数组、链表是线性结构，二叉树、堆是树形结构，它们都有明确的“先后”或“父子”关系，只能描述单一维度的关联。但现实世界中，很多场景的关联是“多对多”的：

• 社交网络：每个人（节点）可以和多个人（节点）建立好友关系（边）；

• 交通路线：每个城市（节点）可以和多个城市（节点）有道路连接（边）；

• 依赖关系：项目中每个任务（节点）可能依赖多个前置任务（边）。

这些“多对多”的关联关系，线性结构和树形结构无法高效描述，而图正是为了解决这类问题而生——它由“节点（Vertex）”和“边（Edge）”组成，节点代表具体对象，边代表对象之间的关联关系，可灵活描述任意复杂的关联场景。

图的核心价值：高效描述多对多关联，提供一套标准化的遍历、查询、路径分析方法，是解决复杂关联问题的核心工具，也是面试中高频考察的进阶知识点（如最短路径、拓扑排序、连通分量）。

二、图的核心概念——面试必记，避免踩坑

图的概念较多，且容易混淆，以下是面试中高频考察的核心概念，必须精准掌握，避免被面试官追问时出错。

1. 图的基本分类

• 按边的方向：分为无向图和有向图（面试重点）

  • 无向图：边没有方向，如社交网络的好友关系（A是B的好友，B也是A的好友）；

  • 有向图：边有方向，如任务依赖（A依赖B，不能反过来表示B依赖A）、网页跳转链接。

• 按边的权重：分为无权图和带权图（面试重点）

  • 无权图：边没有权重，仅表示“是否关联”，如简单的好友关系；

  • 带权图：边有具体数值（权重），如交通路线的距离、网络延迟，核心用于最短路径问题。

• 其他关键分类：

  • 连通图：无向图中，任意两个节点之间都有路径可达；

  • 强连通图：有向图中，任意两个节点之间都有双向路径可达；

  • 稀疏图/稠密图：边的数量远小于节点数的平方（稀疏图），反之则为稠密图（存储方式选择的关键）。

2. 核心术语（必背）

• 节点（Vertex）：图中的对象，如城市、人、任务，通常用整数（0、1、2...）表示，方便编码；

• 边（Edge）：节点之间的关联，无向图用(a,b)表示，有向图用<a,b>表示（a指向b）；

• 度（Degree）：无向图中，节点的度是连接它的边的数量；有向图中，分为入度（指向该节点的边数）和出度（从该节点出发的边数）；

• 路径：从一个节点到另一个节点的边的序列，如A→B→C是一条从A到C的路径；

• 环：起点和终点相同的路径（如A→B→C→A），有向图的环是面试重点（如拓扑排序判断是否有环）。

三、C++图的两种核心存储方式——面试手写必掌握

图的存储方式有多种，面试中最常用、最易手写的是邻接矩阵和邻接表，二者各有优劣，需根据图的类型（稀疏/稠密）选择，这是面试中第一个高频考点（“图如何存储？”）。

1. 邻接矩阵（Adjacency Matrix）—— 稠密图首选

核心思想：用一个二维数组（矩阵）存储图的边，matrix[i][j]表示节点i和节点j之间的关系：

• 无权无向图：matrix[i][j] = 1 表示有边，0 表示无边（且matrix[i][j] = matrix[j][i]）；

• 无权有向图：matrix[i][j] = 1 表示有从i到j的边，0 表示无边（matrix[i][j]≠matrix[j][i]）；

• 带权图：matrix[i][j] = 权重值（如距离、延迟），0或∞表示无边。

优势：查询两个节点是否有边、获取节点的度，时间复杂度O(1)，实现简单；

劣势：空间复杂度O(n²)（n为节点数），稀疏图会浪费大量空间（大部分元素为0）。

面试手写实现（无权无向图，最基础、最易考）：

#include <iostream> #include <vector> using namespace std; // 邻接矩阵实现无向图（面试手写简化版） class GraphMatrix { private: int n; // 节点数量 vector<vector<int>> matrix; // 邻接矩阵 public: // 初始化：n个节点，初始无边 GraphMatrix(int n) : n(n) { matrix.resize(n, vector<int>(n, 0)); // 初始化为0，无边 } // 新增边（无向图：i和j双向关联） void addEdge(int i, int j) { if (i < 0 || i >= n || j < 0 || j >= n) return; // 边界处理，避免越界 matrix[i][j] = 1; matrix[j][i] = 1; // 无向图核心：双向赋值 } // 删除边 void removeEdge(int i, int j) { if (i < 0 || i >= n || j < 0 || j >= n) return; matrix[i][j] = 0; matrix[j][i] = 0; } // 打印邻接矩阵（用于测试，面试可省略） void printGraph() { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout << matrix[i][j] << " "; } cout << endl; } } // 核心接口：获取节点i的邻接节点（面试高频，遍历用） vector<int> getAdjacent(int i) { vector<int> adj; if (i < 0 || i >= n) return adj; for (int j = 0; j < n; j++) { if (matrix[i][j] == 1) { adj.push_back(j); } } return adj; } }; // 测试 int main() { GraphMatrix graph(5); // 5个节点（0-4） graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(1, 3); graph.addEdge(2, 3); graph.addEdge(3, 4); cout << "邻接矩阵：" << endl; graph.printGraph(); cout << "节点0的邻接节点："; vector<int> adj0 = graph.getAdjacent(0); for (int num : adj0) cout << num << " "; // 输出：1 2 return 0; }

2. 邻接表（Adjacency List）—— 稀疏图首选

核心思想：用一个数组（或vector）存储每个节点的邻接节点，数组的索引对应节点编号，每个索引对应的vector存储该节点的所有邻接节点。

优势：空间复杂度O(n + m)（n为节点数，m为边数），稀疏图中空间利用率极高，是面试中最常用的存储方式；

劣势：查询两个节点是否有边，时间复杂度O(k)（k为其中一个节点的度），略逊于邻接矩阵。

面试手写实现（无权有向图，高频考点，带权图可稍作修改）：

#include <iostream> #include <vector> using namespace std; // 邻接表实现有向图（面试手写完整版，可直接复用） class GraphList { private: int n; // 节点数量 vector<vector<int>> adj; // 邻接表：adj[i]存储节点i的所有邻接节点（有向） public: // 初始化：n个节点，初始无邻接节点 GraphList(int n) : n(n) { adj.resize(n); // 每个节点对应一个空的vector } // 新增边（有向图：i指向j，仅添加i→j） void addEdge(int i, int j) { if (i < 0 || i >= n || j < 0 || j >= n) return; // 边界处理 adj[i].push_back(j); // 仅i的邻接表添加j，体现方向 // 无向图只需增加：adj[j].push_back(i); } // 删除边（有向图：删除i→j） void removeEdge(int i, int j) { if (i < 0 || i >= n || j < 0 || j >= n) return; // 遍历adj[i]，找到j并删除 for (auto it = adj[i].begin(); it != adj[i].end(); it++) { if (*it == j) { adj[i].erase(it); break; } } } // 打印邻接表（测试用，面试可省略） void printGraph() { for (int i = 0; i < n; i++) { cout << "节点" << i << "的邻接节点："; for (int j : adj[i]) { cout << j << " "; } cout << endl; } } // 核心接口：获取节点i的邻接节点（遍历、算法核心） vector<int> getAdjacent(int i) { if (i < 0 || i >= n) return {}; return adj[i]; } // 可选接口：获取节点i的出度（有向图面试高频） int getOutDegree(int i) { if (i < 0 || i >= n) return 0; return adj[i].size(); } }; // 测试 int main() { GraphList graph(5); // 5个节点（0-4） graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(1, 3); graph.addEdge(3, 0); // 形成环：0→1→3→0 graph.addEdge(3, 4); cout << "邻接表：" << endl; graph.printGraph(); cout << "节点3的出度：" << graph.getOutDegree(3) << endl; // 输出：2（3→0、3→4） return 0; }

3. 存储方式选择（面试高频追问）

面试官常追问：“什么时候用邻接矩阵，什么时候用邻接表？”，记住以下2点即可应对：

• 稠密图（边数m接近n²，如完全图）：用邻接矩阵，查询效率高，实现简单；

• 稀疏图（边数m远小于n²，如社交网络、交通路线）：用邻接表，节省空间，遍历效率高（无需遍历大量无效的0元素）。

补充：面试中，大部分图相关算法（遍历、最短路径）都基于邻接表实现，因为稀疏图更常见，且邻接表的空间效率更高，建议重点掌握邻接表的手写。

四、图的核心遍历算法——DFS与BFS（面试必考）

图的遍历是所有图算法的基础，面试中必考“深度优先搜索（DFS）”和“广度优先搜索（BFS）”，无论是手写遍历代码，还是在最短路径、拓扑排序中应用，都需要熟练掌握。

核心目标：从指定节点出发，访问图中所有可达节点，且每个节点仅访问一次。

1. 深度优先搜索（DFS）—— 递归/栈实现

核心思想：“一条路走到黑”，从起点出发，优先访问当前节点的邻接节点，直到无法继续前进，再回溯到上一个节点，继续访问其他未访问的邻接节点（类似树的前序遍历）。

实现方式：递归（代码简洁，面试首选）、栈（非递归，避免递归栈溢出，适合大规模图）。

面试手写（基于邻接表，递归版，最易记）：

#include <iostream> #include <vector> using namespace std; // 复用邻接表类（简化版，仅保留核心接口） class GraphList { public: int n; vector<vector<int>> adj; GraphList(int n) : n(n), adj(n) {} void addEdge(int i, int j) { adj[i].push_back(j); } vector<int> getAdjacent(int i) { return adj[i]; } }; // DFS遍历：从start节点出发，访问所有可达节点（递归版） void dfs(GraphList& graph, int start, vector<bool>& visited) { // 标记当前节点为已访问 visited[start] = true; cout << start << " "; // 访问节点（可根据需求修改操作） // 遍历当前节点的所有邻接节点，递归访问未访问的节点 vector<int> adj = graph.getAdjacent(start); for (int neighbor : adj) { if (!visited[neighbor]) { dfs(graph, neighbor, visited); // 递归深入 } } } // 测试DFS int main() { GraphList graph(5); graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(1, 3); graph.addEdge(3, 4); graph.addEdge(2, 3); vector<bool> visited(graph.n, false); // 标记节点是否被访问 cout << "DFS遍历结果（从节点0出发）："; dfs(graph, 0, visited); // 输出：0 1 3 4 2（顺序可能略有不同，取决于邻接表顺序） return 0; }

2. 广度优先搜索（BFS）—— 队列实现

核心思想：“逐层访问”，从起点出发，先访问当前节点的所有邻接节点（第一层），再依次访问每个邻接节点的邻接节点（第二层），直到所有可达节点都被访问（类似树的层序遍历）。

实现方式：必须用队列（queue），先入队当前节点，标记为已访问，再出队，将其未访问的邻接节点入队，循环直至队列为空。

面试手写（基于邻接表，队列版，必背）：

#include <iostream> #include <vector> #include <queue> // BFS必须包含队列头文件 using namespace std; // 复用邻接表类（同上） class GraphList { public: int n; vector<vector<int>> adj; GraphList(int n) : n(n), adj(n) {} void addEdge(int i, int j) { adj[i].push_back(j); } vector<int> getAdjacent(int i) { return adj[i]; } }; // BFS遍历：从start节点出发，访问所有可达节点（队列版） void bfs(GraphList& graph, int start, vector<bool>& visited) { queue<int> q; // 起点入队，标记为已访问 q.push(start); visited[start] = true; while (!q.empty()) { // 出队当前节点，访问 int curr = q.front(); q.pop(); cout << curr << " "; // 遍历当前节点的邻接节点，未访问则入队、标记 vector<int> adj = graph.getAdjacent(curr); for (int neighbor : adj) { if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } } // 测试BFS int main() { GraphList graph(5); graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(1, 3); graph.addEdge(3, 4); graph.addEdge(2, 3); vector<bool> visited(graph.n, false); cout << "BFS遍历结果（从节点0出发）："; bfs(graph, 0, visited); // 输出：0 1 2 3 4（逐层访问，顺序固定） return 0; }

3. DFS与BFS对比（面试高频追问）

关键记住：无权图的最短路径，用BFS；环检测、连通分量，DFS和BFS均可。

五、面试高频图算法——模板化实现，直接套用

图的面试题，本质都是“存储 + 遍历 + 特定逻辑”，以下3个算法是高频考点，掌握模板后，可直接套用解决各类真题。

1. 考点1：环检测（有向图/无向图）

题目场景：判断图中是否存在环（如任务依赖是否有循环、课程安排是否合理），面试中最常考有向图的环检测。

核心思路（DFS版）：用visited标记已访问节点，用recursion标记当前递归路径上的节点；若访问到已在递归路径上的节点，说明存在环。

#include <iostream> #include <vector> using namespace std; class GraphList { public: int n; vector<vector<int>> adj; GraphList(int n) : n(n), adj(n) {} void addEdge(int i, int j) { adj[i].push_back(j); } vector<int> getAdjacent(int i) { return adj[i]; } }; // 有向图环检测（DFS版，面试必写） bool hasCycleDFS(GraphList& graph, int curr, vector<bool>& visited, vector<bool>& recursion) { visited[curr] = true; recursion[curr] = true; // 标记当前节点在递归路径上 for (int neighbor : graph.getAdjacent(curr)) { if (!visited[neighbor]) { // 递归访问邻接节点，若子节点存在环，返回true if (hasCycleDFS(graph, neighbor, visited, recursion)) { return true; } } else if (recursion[neighbor]) { // 邻接节点已访问，且在当前递归路径上，存在环 return true; } } recursion[curr] = false; // 回溯：退出递归路径，取消标记 return false; } // 对外接口：判断有向图是否存在环 bool hasCycle(GraphList& graph) { vector<bool> visited(graph.n, false); vector<bool> recursion(graph.n, false); // 遍历所有节点（处理非连通图） for (int i = 0; i < graph.n; i++) { if (!visited[i]) { if (hasCycleDFS(graph, i, visited, recursion)) { return true; } } } return false; } // 测试 int main() { // 有环图：0→1→3→0 GraphList graph1(4); graph1.addEdge(0, 1); graph1.addEdge(1, 3); graph1.addEdge(3, 0); cout << "图1是否有环：" << (hasCycle(graph1) ? "是" : "否") << endl; // 是 // 无环图：0→1→3→4 GraphList graph2(5); graph2.addEdge(0, 1); graph2.addEdge(1, 3); graph2.addEdge(3, 4); cout << "图2是否有环：" << (hasCycle(graph2) ? "是" : "否") << endl; // 否 return 0; }

2. 考点2：拓扑排序（有向无环图DAG）

题目场景：对有向无环图（DAG）的节点进行排序，使得对于每一条有向边i→j，节点i都在节点j之前（如课程安排、任务调度）。

核心思路（ Kahn算法，BFS版，最易手写）：基于入度统计，先将入度为0的节点入队，依次出队，删除其所有出边（对应节点入度减1），重复此过程，若最终排序的节点数等于总节点数，说明是DAG，否则有环。

#include <iostream> #include <vector> #include <queue> using namespace std; class GraphList { public: int n; vector<vector<int>> adj; GraphList(int n) : n(n), adj(n) {} void addEdge(int i, int j) { adj[i].push_back(j); } vector<int> getAdjacent(int i) { return adj[i]; } }; // 拓扑排序（Kahn算法，BFS版，面试必写） vector<int> topologicalSort(GraphList& graph) { vector<int> inDegree(graph.n, 0); // 存储每个节点的入度 vector<int> result; // 存储拓扑排序结果 queue<int> q; // 1. 统计每个节点的入度 for (int i = 0; i < graph.n; i++) { for (int neighbor : graph.getAdjacent(i)) { inDegree[neighbor]++; } } // 2. 将入度为0的节点入队 for (int i = 0; i < graph.n; i++) { if (inDegree[i] == 0) { q.push(i); } } // 3. BFS遍历，生成拓扑排序 while (!q.empty()) { int curr = q.front(); q.pop(); result.push_back(curr); // 遍历当前节点的邻接节点，入度减1 for (int neighbor : graph.getAdjacent(curr)) { inDegree[neighbor]--; // 入度为0，入队 if (inDegree[neighbor] == 0) { q.push(neighbor); } } } // 若结果长度不等于节点数，说明有环，无法拓扑排序 if (result.size() != graph.n) { return {}; // 有环，返回空 } return result; } // 测试 int main() { // 有向无环图：0→1→3，0→2→3，3→4 GraphList graph(5); graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(1, 3); graph.addEdge(2, 3); graph.addEdge(3, 4); vector<int> topo = topologicalSort(graph); if (topo.empty()) { cout << "图有环，无法拓扑排序" << endl; } else { cout << "拓扑排序结果："; for (int num : topo) { cout << num << " "; // 输出：0 1 2 3 4（或0 2 1 3 4） } } return 0; }

3. 考点3：最短路径（无权图/BFS，带权图/Dijkstra）

题目场景：求两个节点之间的最短路径（如交通路线最短距离、网络延迟最小），面试中常考“无权图”和“带权无负权图”。

核心思路：

• 无权图：用BFS（逐层访问，第一层距离1，第二层距离2，以此类推）；

• 带权无负权图：用Dijkstra算法（贪心思想，每次选择距离起点最近的节点，更新其邻接节点的距离）。

面试手写（无权图最短路径，BFS版；带权图Dijkstra，优先队列版）：

#include <iostream> #include <vector> #include <queue> #include <climits> // 用于INT_MAX using namespace std; // 一、无权图最短路径（BFS版） class GraphList { public: int n; vector<vector<int>> adj; GraphList(int n) : n(n), adj(n) {} void addEdge(int i, int j) { adj[i].push_back(j); adj[j].push_back(i); } // 无向图 vector<int> getAdjacent(int i) { return adj[i]; } }; // 无权图：求start到所有节点的最短距离 vector<int> shortestPathUnweighted(GraphList& graph, int start) { vector<int> dist(graph.n, -1); // dist[i]表示start到i的距离，-1表示不可达 queue<int> q; dist[start] = 0; // 起点距离为0 q.push(start); while (!q.empty()) { int curr = q.front(); q.pop(); for (int neighbor : graph.getAdjacent(curr)) { if (dist[neighbor] == -1) { // 未访问过 dist[neighbor] = dist[curr] + 1; // 距离+1 q.push(neighbor); } } } return dist; } // 二、带权无负权图最短路径（Dijkstra算法，优先队列版） class WeightedGraph { public: int n; // 邻接表：adj[i]存储pair<邻接节点, 权重> vector<vector<pair<int, int>>> adj; WeightedGraph(int n) : n(n), adj(n) {} void addEdge(int i, int j, int weight) { adj[i].emplace_back(j, weight); // 有向带权边 // 无向带权边需增加：adj[j].emplace_back(i, weight); } }; // Dijkstra算法：求start到所有节点的最短距离（无负权边） vector<int> dijkstra(WeightedGraph& graph, int start) { vector<int> dist(graph.n, INT_MAX); // 初始距离为无穷大 // 优先队列：pair<距离, 节点>，按距离从小到大排序（小根堆） priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; dist[start] = 0; pq.emplace(0, start); while (!pq.empty()) { auto [currDist, curr] = pq.top(); pq.pop(); // 若当前距离大于已记录的距离，跳过（已找到更优路径） if (currDist > dist[curr]) { continue; } // 更新邻接节点的距离 for (auto [neighbor, weight] : graph.adj[curr]) { if (dist[neighbor] > dist[curr] + weight) { dist[neighbor] = dist[curr] + weight; pq.emplace(dist[neighbor], neighbor); } } } return dist; } // 测试 int main() { // 测试无权图最短路径 GraphList graph1(5); graph1.addEdge(0, 1); graph1.addEdge(0, 2); graph1.addEdge(1, 3); graph1.addEdge(2, 3); graph1.addEdge(3, 4); vector<int> dist1 = shortestPathUnweighted(graph1, 0); cout << "无权图：0到4的最短距离：" << dist1[4] << endl; // 输出：2（0→1→3→4 或 0→2→3→4，距离3？修正：0到3是2，3到4是1，总3） // 测试带权图Dijkstra WeightedGraph graph2(4); graph2.addEdge(0, 1, 2); graph2.addEdge(0, 2, 5); graph2.addEdge(1, 2, 1); graph2.addEdge(1, 3, 3); graph2.addEdge(2, 3, 1); vector<int> dist2 = dijkstra(graph2, 0); cout << "带权图：0到3的最短距离：" << dist2[3] << endl; // 输出：4（0→1→2→3：2+1+1=4） return 0; }

六、面试避坑指南与学习建议

1. 常见避坑点（丢分重灾区）

• 坑1：混淆无向图和有向图的存储/遍历——无向图addEdge需双向赋值，有向图仅单向赋值，遍历时有向图需注意边的方向；

• 坑2：DFS递归忘记回溯——如环检测中，recursion数组未在递归结束后置为false，导致误判环；

• 坑3：Dijkstra算法使用错误——带权图用BFS求最短路径，或未处理“当前距离大于已记录距离”的情况，导致结果错误；

• 坑4：忽略非连通图——遍历、环检测、拓扑排序时，未遍历所有节点，仅处理了起点所在的连通分量；

• 坑5：邻接表删除边时，未遍历找到对应节点就删除，导致删除失败（如直接erase(adj[i].begin() + j)，而非遍历查找）。

2. 学习建议（高效应对面试）

• 1. 先掌握存储，再攻克算法：优先手写邻接表（稀疏图常用）和邻接矩阵，理解二者的区别和适用场景，这是所有图算法的基础；

• 2. 熟练DFS和BFS：每天手写1遍递归版DFS、队列版BFS，做到脱稿，它们是图算法的“万能工具”；

• 3. 模板化记忆高频算法：环检测、拓扑排序、Dijkstra算法，记住核心思路和模板代码，面试时直接套用，重点修改存储方式和逻辑细节；

• 4. 多刷真题巩固：LeetCode 207（课程表，拓扑排序）、743（网络延迟，Dijkstra）、200（岛屿数量，DFS/BFS），这些真题覆盖了图的核心考点；

• 5. 注意边界处理：面试中，节点越界、非连通图、空图等边界情况，能体现代码的健壮性，务必添加（如判断i、j是否在0~n-1范围内）。

总结

图是C++数据结构进阶中最灵活、也最考验综合能力的知识点，核心不在于“记住多少概念”，而在于“掌握存储方式 + 灵活运用遍历算法 + 适配场景选择算法”。

面试中，图的考察主要围绕“存储（邻接表/邻接矩阵）、遍历（DFS/BFS）、环检测、拓扑排序、最短路径”这5个核心点，只要能熟练手写邻接表、DFS、BFS，记住高频算法的模板，就能轻松应对各类图相关考题。

小练习：用DFS解决“岛屿数量”问题（LeetCode 200），试试能不能结合图的遍历思路写出代码？欢迎在评论区交流你的思路～