1. 项目概述为什么图是数据结构中的“瑞士军刀”如果你已经学过了线性表、栈、队列和树那么恭喜你你的数据结构工具箱已经相当丰富了。但当你面对诸如社交网络的好友关系、地图导航的最短路径、任务之间的依赖调度甚至是编译器分析程序的控制流时你会发现之前那些“规规矩矩”的结构有点力不从心。这时候就该“图”这位全能选手登场了。它不像数组那样要求元素排排坐也不像树那样有严格的父子层级图的核心思想是“连接”它用一种极其灵活的方式描述事物之间多对多的复杂关系。我最初接触图时觉得它概念繁多顶点、边、有向、无向、权重、度……有点让人望而生畏。但真正用代码实现几个经典算法后我才恍然大悟图的强大恰恰源于它对现实世界复杂关系的抽象能力。一个精心设计的图结构配上高效的算法能解决许多看似棘手的问题。今天我们就抛开那些枯燥的定义直接从“如何用代码把图构建出来”这个最实在的角度切入手把手带你实现两种最核心的存储结构——邻接矩阵和邻接表并用C把它们写出来。无论你是正在备战期末考试还是准备技术面试或者单纯想提升自己的编程内功这篇内容都能给你提供可以直接“抄作业”的代码和避坑指南。2. 核心概念速览五分钟建立图的世界观在动手写代码之前我们得先统一“语言”。图的理论概念是它的骨架理解这些你才能知道代码每一部分在为什么服务。2.1 顶点与边图的原子与纽带一切图的基础都由两部分构成顶点和边。顶点也叫节点就是我们要研究的实体对象。比如在社交网络里每个用户就是一个顶点在地图导航里每个十字路口或地点就是一个顶点。在代码中我们通常用从0或1开始的整数编号来标识它们这样方便用数组索引。边连接两个顶点的关系。边才是图表达信息的核心。边可以分为几类无向边就像朋友关系如果A是B的朋友那么B也一定是A的朋友。边(A, B)和(B, A)是同一条边。有向边就像微博的关注A关注了B并不意味着B关注了A。边(A, B)和(B, A)是两条不同的边。带权边边有了“附加值”。比如地图上两个地点之间的道路长度、网络传输的带宽成本、任务完成的所需时间。这个值就是权重。2.2 度、路径与连通性图的“体检报告”理解了基本组成我们再来看看如何描述一个图的特性。度一个顶点的“社交活跃度”。对于无向图顶点的度就是与它相连的边的条数。对于有向图则分为入度有多少条边指向它和出度它指向多少条边。在社交网络分析中度很高的顶点可能就是“网红”或关键人物。路径从一个顶点到另一个顶点沿着边“走”过去的一系列顶点序列。比如从家到公司可能经过“家-地铁站A-地铁站B-公司”这样一条路径。连通性这是图一个非常重要的全局性质。在无向图中如果任意两个顶点之间都存在路径那么这个图就是连通图。否则它可能由几个互不连通的“岛屿”连通分量组成。对于有向图如果任意两个顶点可以互相到达注意是双向则称为强连通图。注意很多初学者容易混淆“边数多”和“连通”。一个图可能边很多但如果有一个顶点孤零零的它就不是连通图。判断连通性通常需要运行一遍深度优先搜索或广度优先搜索来验证。2.3 两种核心存储结构的选择困境如何把上面这些概念塞进计算机内存里这就是存储结构要解决的问题。主流有两种它们各有胜负选择哪一种完全取决于你面对的是一个什么样的图。邻接矩阵简单粗暴的“表格法”。怎么存用一个V x V的二维数组V是顶点数。如果matrix[i][j] 1或权重值就表示顶点i到顶点j有一条边对于无向图matrix[j][i]也要同步设置。优点直观一眼就能看出任意两个点之间有没有边。查询快判断顶点i和j之间是否有边或者获取权重时间复杂度是O(1)直接数组索引。对稠密图友好当图的边数接近顶点数的平方时空间利用率高。缺点空间开销大需要O(V^2)的空间。对于一个有10000个顶点的稀疏社交网络平均每人关注几百人矩阵里绝大部分都是0极其浪费。添加/删除顶点麻烦需要动态调整二维数组大小成本高。邻接表灵活高效的“链表法”现代常用动态数组替代链表。怎么存为每个顶点维护一个列表可以是数组、链表等里面存储所有与它直接相连的邻居顶点对于有向图通常存出边邻居。这个列表就叫这个顶点的邻接表。优点空间效率高只存储实际存在的边空间复杂度为O(V E)对于稀疏图优势巨大。遍历邻居高效要找出一个顶点的所有邻居直接遍历它的邻接表即可非常符合图算法的常见操作。动态增删边方便。缺点查询边慢要判断i到j是否有边需要遍历i的邻接表时间复杂度O(degree(i))在最坏情况下可能是O(V)。实现稍复杂需要管理多个动态列表。如何选择我个人的经验法则是如果题目明确是稠密图或者需要频繁进行任意两点间边的存在性查询用邻接矩阵。除此之外绝大多数情况特别是算法竞赛和面试中邻接表用vector实现是默认首选因为它更通用也更节省内存。3. 邻接矩阵实现详解从设计到编码理论说够了我们上代码。首先实现邻接矩阵。我们会实现一个通用的、支持带权图的类。3.1 类的设计与成员变量我们的目标是设计一个类既能表示无向图也能表示有向图既能表示简单图边权为1也能表示带权图。这里采用一个常见且灵活的设计用vectorvectorint作为矩阵底层用一个布尔标志directed来区分有向/无向。#include iostream #include vector #include iomanip // 用于格式化输出 class AdjacencyMatrixGraph { private: int numVertices; // 顶点数量 bool isDirected; // 是否为有向图 bool isWeighted; // 是否为带权图 std::vectorstd::vectorint matrix; // 邻接矩阵 // 使用int矩阵对于非带权图1表示有边0表示无边。 // 对于带权图存储权重值可以用一个特殊值如0或INT_MAX表示无边。 // 注意这里假设权重为整数且非负。如果权重可能为负或浮点需改为double或自定义类型。 public: // 构造函数 AdjacencyMatrixGraph(int V, bool directed false, bool weighted false) : numVertices(V), isDirected(directed), isWeighted(weighted) { // 初始化一个 V x V 的矩阵所有元素初始化为0表示无边 matrix.resize(V, std::vectorint(V, 0)); // 如果是带权图0可能是一个有效的权重所以我们需要一个“无穷大”或特殊值来表示无边。 // 但为了简单起见本例中0仍表示无边。实际应用中需根据权重范围调整。 } // ... 其他成员函数将在下文实现 };实操心得将isDirected和isWeighted作为构造参数非常有用。它让我们的图类变得通用。在算法题中你通常能提前知道图的类型用对应的标志初始化即可避免写多个类似的类。3.2 边的添加、删除与查询操作这是图类的核心功能。我们需要仔细处理有向/无向、带权/非带权的区别。// 添加边 (u, v) void addEdge(int u, int v, int weight 1) { if (u 0 || u numVertices || v 0 || v numVertices) { std::cerr Error: Vertex index out of range! std::endl; return; } if (u v) { std::cerr Warning: Self-loop detected. Ignored in simple graph representation. std::endl; return; // 简单图通常不考虑自环可根据需求修改 } matrix[u][v] isWeighted ? weight : 1; // 带权图存权重否则存1 if (!isDirected) { // 如果是无向图矩阵是对称的 matrix[v][u] isWeighted ? weight : 1; } } // 删除边 (u, v) void removeEdge(int u, int v) { if (u 0 || u numVertices || v 0 || v numVertices) { std::cerr Error: Vertex index out of range! std::endl; return; } matrix[u][v] 0; // 设为0表示无边 if (!isDirected) { matrix[v][u] 0; } } // 查询边 (u, v) 是否存在或权重 int getEdge(int u, int v) const { if (u 0 || u numVertices || v 0 || v numVertices) { std::cerr Error: Vertex index out of range! std::endl; return -1; // 或抛异常 } return matrix[u][v]; // 返回0表示无边非0表示有边或权重 } // 判断边是否存在 bool hasEdge(int u, int v) const { return getEdge(u, v) ! 0; }关键点解析下标检查这是必须的防止数组越界导致程序崩溃。在实际项目中可能会用异常替代cerr输出。自环处理在简单图的邻接矩阵表示中对角线元素matrix[i][i]通常没有意义或表示自环。这里选择忽略自环添加。如果你的应用需要自环可以移除这个判断。对称性对于无向图添加或删除边时必须同时操作matrix[u][v]和matrix[v][u]以保持矩阵的对称性。这是最容易出错的地方之一。权重存储我们用一个int矩阵通吃。对于非带权图用1表示有边清晰直观。对于带权图0可能是一个合法的权重比如成本为0的路径这是一个设计缺陷。更严谨的做法是使用std::vectorstd::vectorint*并用nullptr表示无边或者使用一个单独的bool矩阵记录边是否存在。但为了代码简洁和教学清晰本例做了妥协。在解决具体问题时你需要根据权重范围来调整这个“无边”的表示值例如如果权重都是正数可以用-1或INT_MAX表示无边。3.3 图的遍历与信息打印虽然深度优先搜索和广度优先搜索通常作为独立算法实现但作为图类提供一个直观的打印方法来查看结构是非常有用的调试手段。// 打印邻接矩阵 void printMatrix() const { std::cout Adjacency Matrix ( numVertices vertices, (isDirected ? Directed : Undirected) , (isWeighted ? Weighted : Unweighted) ):\n; std::cout ; for (int i 0; i numVertices; i) { std::cout std::setw(3) i; // 设置列宽为3对齐 } std::cout \n; for (int i 0; i numVertices; i) { std::cout std::setw(2) i :; for (int j 0; j numVertices; j) { std::cout std::setw(3) matrix[i][j]; } std::cout \n; } } // 获取顶点数量 int getNumVertices() const { return numVertices; } // 获取所有邻居对于无向图是相连顶点对于有向图是出边邻居 std::vectorint getNeighbors(int v) const { std::vectorint neighbors; for (int i 0; i numVertices; i) { if (matrix[v][i] ! 0) { // 有边 neighbors.push_back(i); } } return neighbors; }printMatrix函数能让你一目了然地看到整个图的连接情况在调试小规模图时极其方便。getNeighbors函数则是为后续实现图遍历算法准备的接口。4. 邻接表实现详解更通用的选择现在来实现更常用、更高效的邻接表。我们将使用C的vector来存储每个顶点的邻居列表因为vector的缓存友好性和易用性通常优于链表。4.1 结构定义与类设计在邻接表中我们需要存储每个邻居顶点以及可能的边权重。因此我们首先定义一个Edge结构体或直接用pair。#include iostream #include vector #include utility // for std::pair // 定义边的结构体存储目标顶点和权重 struct Edge { int to; // 目标顶点 int weight; // 边权重对于非带权图默认为1 Edge(int t, int w 1) : to(t), weight(w) {} }; class AdjacencyListGraph { private: int numVertices; bool isDirected; bool isWeighted; std::vectorstd::vectorEdge adjList; // 邻接表每个顶点对应一个Edge列表 public: // 构造函数 AdjacencyListGraph(int V, bool directed false, bool weighted false) : numVertices(V), isDirected(directed), isWeighted(weighted) { adjList.resize(V); // 初始化V个空的邻居列表 } // ... 其他成员函数 };这里adjList[i]是一个vectorEdge存储了从顶点i出发的所有边。这种设计清晰地将顶点和其关联的边绑定在一起。4.2 边的增删查改实现邻接表的边操作逻辑与矩阵不同主要是在列表中进行查找、插入和删除。// 添加边 (u, v) void addEdge(int u, int v, int weight 1) { if (u 0 || u numVertices || v 0 || v numVertices) { std::cerr Error: Vertex index out of range! std::endl; return; } if (u v) { // 邻接表可以处理自环这里选择添加 adjList[u].push_back(Edge(v, isWeighted ? weight : 1)); return; } adjList[u].push_back(Edge(v, isWeighted ? weight : 1)); if (!isDirected) { // 无向图需要添加反向边 adjList[v].push_back(Edge(u, isWeighted ? weight : 1)); } // 注意邻接表默认允许平行边重复边。如果需要禁止需要在添加前遍历adjList[u]检查是否已存在边(u, v)。 } // 删除边 (u, v) - 效率较低因为需要遍历列表查找 void removeEdge(int u, int v) { if (u 0 || u numVertices || v 0 || v numVertices) { return; } // 删除从u到v的边 for (auto it adjList[u].begin(); it ! adjList[u].end(); it) { if (it-to v) { adjList[u].erase(it); break; // 假设简单图最多一条边 } } if (!isDirected) { // 如果是无向图还要删除从v到u的边 for (auto it adjList[v].begin(); it ! adjList[v].end(); it) { if (it-to u) { adjList[v].erase(it); break; } } } } // 查询边 (u, v) 的权重不存在则返回一个特定值如-1或0 int getEdgeWeight(int u, int v) const { if (u 0 || u numVertices || v 0 || v numVertices) { return -1; // 表示错误或无边 } for (const Edge e : adjList[u]) { if (e.to v) { return e.weight; } } return 0; // 用0表示无边假设权重为正或用-1等 } bool hasEdge(int u, int v) const { return getEdgeWeight(u, v) ! 0; // 根据getEdgeWeight的返回值定义调整 }关键点解析与避坑平行边处理上面的addEdge实现允许平行边即多条相同的(u,v)边。这在某些场景下是需要的比如流量网络中的多条管道。但如果你的算法或问题假设是简单图没有平行边你必须在添加前遍历adjList[u]检查是否已存在到v的边。这是一个常见的面试考点。删除效率在vector中删除中间元素的时间复杂度是O(n)因为需要移动后续元素。如果图需要频繁删边且性能敏感可以考虑使用std::list作为邻接表的底层容器但会牺牲缓存局部性。另一种常见做法是“懒惰删除”即标记边为无效在后续遍历时跳过。查询效率hasEdge和getEdgeWeight需要遍历列表最坏情况O(V)。这是邻接表的主要缺点。如果应用需要频繁的边存在性查询可能需要额外维护一个哈希表来加速。4.3 遍历接口与实用方法邻接表最自然的操作就是遍历某个顶点的所有邻居这恰好是大多数图算法如BFS、DFS、Dijkstra的核心操作。// 获取顶点v的所有出边邻居对于无向图就是所有相邻顶点 const std::vectorEdge getNeighbors(int v) const { // 返回常引用避免拷贝同时防止外部修改内部数据 if (v 0 || v numVertices) { static const std::vectorEdge empty; // 返回一个空向量的引用 return empty; } return adjList[v]; } // 打印邻接表 void printList() const { std::cout Adjacency List ( numVertices vertices, (isDirected ? Directed : Undirected) , (isWeighted ? Weighted : Unweighted) ):\n; for (int i 0; i numVertices; i) { std::cout i : ; for (const Edge e : adjList[i]) { std::cout - ( e.to; if (isWeighted) { std::cout , w: e.weight; } std::cout ) ; } std::cout \n; } } int getNumVertices() const { return numVertices; } bool isGraphDirected() const { return isDirected; } bool isGraphWeighted() const { return isWeighted; }getNeighbors返回一个const引用这是关键的性能优化。图算法中会无数次调用这个函数来获取邻居如果每次返回拷贝当图很大时开销巨大。返回引用避免了拷贝同时用const保证图的结构不会被意外修改。5. 两种实现的对比与性能实测纸上得来终觉浅我们写个简单的测试程序从空间和时间上感受一下两者的差异。#include chrono #include random void testPerformance() { const int V 5000; // 顶点数 const double density 0.01; // 边密度1%的边存在这是一个稀疏图 std::random_device rd; std::mt19937 gen(rd()); std::uniform_int_distribution dis(0, V-1); std::uniform_int_distribution weight_dis(1, 100); // 测试邻接矩阵 auto start std::chrono::high_resolution_clock::now(); AdjacencyMatrixGraph matGraph(V, false, true); long long edgeCount static_castlong long(V * V * density); for (long long i 0; i edgeCount; i) { int u dis(gen); int v dis(gen); int w weight_dis(gen); matGraph.addEdge(u, v, w); } auto end std::chrono::high_resolution_clock::now(); auto duration_mat std::chrono::duration_caststd::chrono::milliseconds(end - start); std::cout Adjacency Matrix build time for edgeCount edges: duration_mat.count() ms std::endl; // 估算内存V*V * sizeof(int) bytes size_t mem_mat V * V * sizeof(int); std::cout Estimated memory: mem_mat / (1024 * 1024) MB std::endl; // 测试邻接表 start std::chrono::high_resolution_clock::now(); AdjacencyListGraph listGraph(V, false, true); for (long long i 0; i edgeCount; i) { int u dis(gen); int v dis(gen); int w weight_dis(gen); listGraph.addEdge(u, v, w); } end std::chrono::high_resolution_clock::now(); auto duration_list std::chrono::duration_caststd::chrono::milliseconds(end - start); std::cout Adjacency List build time for edgeCount edges: duration_list.count() ms std::endl; // 估算内存V * sizeof(vector) 2*E * sizeof(Edge) (无向图每条边存两次) size_t mem_list V * sizeof(std::vectorEdge) 2 * edgeCount * sizeof(Edge); std::cout Estimated memory: mem_list / (1024 * 1024) MB std::endl; // 测试查询性能随机查询10000次 const int queryTimes 10000; start std::chrono::high_resolution_clock::now(); int dummySum 0; // 防止编译器优化掉查询 for (int i 0; i queryTimes; i) { int u dis(gen); int v dis(gen); if (matGraph.hasEdge(u, v)) { dummySum matGraph.getEdge(u, v); } } end std::chrono::high_resolution_clock::now(); auto duration_mat_query std::chrono::duration_caststd::chrono::microseconds(end - start); std::cout Matrix edge query time: duration_mat_query.count() us std::endl; start std::chrono::high_resolution_clock::now(); dummySum 0; for (int i 0; i queryTimes; i) { int u dis(gen); int v dis(gen); if (listGraph.hasEdge(u, v)) { dummySum listGraph.getEdgeWeight(u, v); } } end std::chrono::high_resolution_clock::now(); auto duration_list_query std::chrono::duration_caststd::chrono::microseconds(end - start); std::cout List edge query time: duration_list_query.count() us std::endl; }运行这个测试顶点数5000边密度1%约25万条边你可能会看到类似下面的结果构建时间邻接表可能略慢因为需要多次动态分配内存push_back。内存占用邻接矩阵固定占用约5000*5000*4 bytes ≈ 100MB。而邻接表只存储实际边约2*250000*8 bytes ≈ 4MB假设Edge结构体8字节对齐。内存节省了两个数量级查询时间邻接矩阵的查询是稳定的O(1)极快。邻接表的查询需要遍历列表在稀疏图中平均很快但最坏情况下是O(V)且受缓存影响总体会比矩阵慢。这个测试清晰地印证了之前的理论分析对于稀疏图邻接表在空间上具有压倒性优势而这是大多数实际场景的常态。牺牲一点查询时间换来巨大的空间节省是非常划算的。6. 常见问题与实战排坑指南在实际实现和使用图结构时你会遇到各种各样的问题。下面是我踩过的一些坑和对应的解决方案。6.1 顶点编号从0开始还是从1开始这是一个看似简单却容易引发混乱的问题。C标准库和大多数算法约定数组、vector索引从0开始。因此将顶点编号为0到V-1是最自然、最不容易出错的选择。你上面看到的代码都是基于0起始的。问题输入习惯很多算法题或教科书示例的输入顶点编号是从1开始的。解决方案在读取输入后立即将所有顶点编号减1转换为0起始的内部表示。在输出结果时再加1转换回去。永远在内部使用0起始编号这能避免大量的下标计算错误。可以在图类构造函数或addEdge方法中封装这个转换逻辑。6.2 如何高效判断边是否存在针对邻接表邻接表的hasEdge是O(degree)操作如果频繁调用比如在某些特定算法中会成为瓶颈。方案一使用unordered_set存储邻居。将adjList的类型从vectorEdge改为vectorunordered_setint或vectorunordered_mapint, int后者同时存储权重。这样hasEdge和getEdgeWeight可以降到平均O(1)。但代价是遍历所有邻居时这是更常见的操作的常数时间变大且内存开销增加。方案二空间换时间维护一个矩阵副本。对于需要频繁边查询但又想用邻接表遍历的场景可以同时维护一个vectorvectorbool的hasEdge矩阵。但这几乎等同于邻接矩阵的空间开销。方案三算法优化。很多时候你并不需要频繁的随机边查询。标准的BFS/DFS/Dijkstra等算法核心操作是“获取顶点v的所有邻居并处理”这正是邻接表的强项。重新审视你的算法看是否真的需要那么多hasEdge调用。6.3 处理大规模图时的内存优化技巧当顶点数超过10万即使使用邻接表内存也可能紧张。使用vectorint压缩存储如果不带权重每个邻居只存目标顶点int。如果带权重可以使用vectorpairint, int或者两个vector一个存目标顶点一个存权重。pair和struct Edge相比可能节省一些内存对齐带来的开销。使用前向星这是一种用两个大数组head,edges模拟邻接表的方法常见于ACM竞赛中内存使用非常紧凑且遍历效率高。但对于动态增删边不友好。考虑使用uint32_t而非int如果顶点数小于2^32使用uint32_t可以节省一半内存在64位系统上int通常是4字节但结构体对齐可能占用8字节。使用内存池如果图结构固定可以使用自定义分配器来减少vector动态扩容和内存碎片。6.4 邻接表遍历中的迭代器失效问题这是一个经典的C STL陷阱。当你在遍历某个顶点的邻居列表adjList[v]时如果遍历过程中修改了这个列表比如删除了一条边可能会导致迭代器失效程序崩溃。// 错误示例遍历时删除满足条件的边 for (auto it adjList[v].begin(); it ! adjList[v].end(); it) { if (someCondition(*it)) { adjList[v].erase(it); // 删除后it失效后续it行为未定义 } } // 正确写法使用erase-remove惯用法或后向遍历 auto vec adjList[v]; vec.erase(std::remove_if(vec.begin(), vec.end(), [](const Edge e) { return someCondition(e); }), vec.end()); // 或者如果必须用循环且只删除一个元素可以这样效率较低 for (auto it adjList[v].begin(); it ! adjList[v].end(); ) { if (someCondition(*it)) { it adjList[v].erase(it); // erase返回下一个有效迭代器 } else { it; } }在编写图算法时尤其是涉及修改图结构的算法如最小生成树的Kruskal算法需要删边不通常不直接删但类似场景一定要警惕迭代器失效。6.5 如何为图算法提供统一的接口你可能会实现多种图算法BFS, DFS, Dijkstra, Prim等。一个好的设计是让这些算法接收一个“图接口”作为参数而不是具体的AdjacencyListGraph或AdjacencyMatrixGraph类。这需要用到抽象基类接口类。class Graph { public: virtual ~Graph() default; virtual int getNumVertices() const 0; virtual const std::vectorEdge getNeighbors(int v) const 0; virtual bool hasEdge(int u, int v) const 0; virtual int getEdgeWeight(int u, int v) const 0; // ... 其他必要接口 }; // 让AdjacencyListGraph和AdjacencyMatrixGraph都继承自Graph并实现这些虚函数。这样你的dijkstra(Graph g, int source)函数就可以处理任何实现了Graph接口的图类大大提高了代码的复用性和可测试性。这是面向对象设计在数据结构中的应用在大型项目中非常有用。 C++实现图的邻接矩阵与邻接表：核心存储结构详解与性能对比
1. 项目概述为什么图是数据结构中的“瑞士军刀”如果你已经学过了线性表、栈、队列和树那么恭喜你你的数据结构工具箱已经相当丰富了。但当你面对诸如社交网络的好友关系、地图导航的最短路径、任务之间的依赖调度甚至是编译器分析程序的控制流时你会发现之前那些“规规矩矩”的结构有点力不从心。这时候就该“图”这位全能选手登场了。它不像数组那样要求元素排排坐也不像树那样有严格的父子层级图的核心思想是“连接”它用一种极其灵活的方式描述事物之间多对多的复杂关系。我最初接触图时觉得它概念繁多顶点、边、有向、无向、权重、度……有点让人望而生畏。但真正用代码实现几个经典算法后我才恍然大悟图的强大恰恰源于它对现实世界复杂关系的抽象能力。一个精心设计的图结构配上高效的算法能解决许多看似棘手的问题。今天我们就抛开那些枯燥的定义直接从“如何用代码把图构建出来”这个最实在的角度切入手把手带你实现两种最核心的存储结构——邻接矩阵和邻接表并用C把它们写出来。无论你是正在备战期末考试还是准备技术面试或者单纯想提升自己的编程内功这篇内容都能给你提供可以直接“抄作业”的代码和避坑指南。2. 核心概念速览五分钟建立图的世界观在动手写代码之前我们得先统一“语言”。图的理论概念是它的骨架理解这些你才能知道代码每一部分在为什么服务。2.1 顶点与边图的原子与纽带一切图的基础都由两部分构成顶点和边。顶点也叫节点就是我们要研究的实体对象。比如在社交网络里每个用户就是一个顶点在地图导航里每个十字路口或地点就是一个顶点。在代码中我们通常用从0或1开始的整数编号来标识它们这样方便用数组索引。边连接两个顶点的关系。边才是图表达信息的核心。边可以分为几类无向边就像朋友关系如果A是B的朋友那么B也一定是A的朋友。边(A, B)和(B, A)是同一条边。有向边就像微博的关注A关注了B并不意味着B关注了A。边(A, B)和(B, A)是两条不同的边。带权边边有了“附加值”。比如地图上两个地点之间的道路长度、网络传输的带宽成本、任务完成的所需时间。这个值就是权重。2.2 度、路径与连通性图的“体检报告”理解了基本组成我们再来看看如何描述一个图的特性。度一个顶点的“社交活跃度”。对于无向图顶点的度就是与它相连的边的条数。对于有向图则分为入度有多少条边指向它和出度它指向多少条边。在社交网络分析中度很高的顶点可能就是“网红”或关键人物。路径从一个顶点到另一个顶点沿着边“走”过去的一系列顶点序列。比如从家到公司可能经过“家-地铁站A-地铁站B-公司”这样一条路径。连通性这是图一个非常重要的全局性质。在无向图中如果任意两个顶点之间都存在路径那么这个图就是连通图。否则它可能由几个互不连通的“岛屿”连通分量组成。对于有向图如果任意两个顶点可以互相到达注意是双向则称为强连通图。注意很多初学者容易混淆“边数多”和“连通”。一个图可能边很多但如果有一个顶点孤零零的它就不是连通图。判断连通性通常需要运行一遍深度优先搜索或广度优先搜索来验证。2.3 两种核心存储结构的选择困境如何把上面这些概念塞进计算机内存里这就是存储结构要解决的问题。主流有两种它们各有胜负选择哪一种完全取决于你面对的是一个什么样的图。邻接矩阵简单粗暴的“表格法”。怎么存用一个V x V的二维数组V是顶点数。如果matrix[i][j] 1或权重值就表示顶点i到顶点j有一条边对于无向图matrix[j][i]也要同步设置。优点直观一眼就能看出任意两个点之间有没有边。查询快判断顶点i和j之间是否有边或者获取权重时间复杂度是O(1)直接数组索引。对稠密图友好当图的边数接近顶点数的平方时空间利用率高。缺点空间开销大需要O(V^2)的空间。对于一个有10000个顶点的稀疏社交网络平均每人关注几百人矩阵里绝大部分都是0极其浪费。添加/删除顶点麻烦需要动态调整二维数组大小成本高。邻接表灵活高效的“链表法”现代常用动态数组替代链表。怎么存为每个顶点维护一个列表可以是数组、链表等里面存储所有与它直接相连的邻居顶点对于有向图通常存出边邻居。这个列表就叫这个顶点的邻接表。优点空间效率高只存储实际存在的边空间复杂度为O(V E)对于稀疏图优势巨大。遍历邻居高效要找出一个顶点的所有邻居直接遍历它的邻接表即可非常符合图算法的常见操作。动态增删边方便。缺点查询边慢要判断i到j是否有边需要遍历i的邻接表时间复杂度O(degree(i))在最坏情况下可能是O(V)。实现稍复杂需要管理多个动态列表。如何选择我个人的经验法则是如果题目明确是稠密图或者需要频繁进行任意两点间边的存在性查询用邻接矩阵。除此之外绝大多数情况特别是算法竞赛和面试中邻接表用vector实现是默认首选因为它更通用也更节省内存。3. 邻接矩阵实现详解从设计到编码理论说够了我们上代码。首先实现邻接矩阵。我们会实现一个通用的、支持带权图的类。3.1 类的设计与成员变量我们的目标是设计一个类既能表示无向图也能表示有向图既能表示简单图边权为1也能表示带权图。这里采用一个常见且灵活的设计用vectorvectorint作为矩阵底层用一个布尔标志directed来区分有向/无向。#include iostream #include vector #include iomanip // 用于格式化输出 class AdjacencyMatrixGraph { private: int numVertices; // 顶点数量 bool isDirected; // 是否为有向图 bool isWeighted; // 是否为带权图 std::vectorstd::vectorint matrix; // 邻接矩阵 // 使用int矩阵对于非带权图1表示有边0表示无边。 // 对于带权图存储权重值可以用一个特殊值如0或INT_MAX表示无边。 // 注意这里假设权重为整数且非负。如果权重可能为负或浮点需改为double或自定义类型。 public: // 构造函数 AdjacencyMatrixGraph(int V, bool directed false, bool weighted false) : numVertices(V), isDirected(directed), isWeighted(weighted) { // 初始化一个 V x V 的矩阵所有元素初始化为0表示无边 matrix.resize(V, std::vectorint(V, 0)); // 如果是带权图0可能是一个有效的权重所以我们需要一个“无穷大”或特殊值来表示无边。 // 但为了简单起见本例中0仍表示无边。实际应用中需根据权重范围调整。 } // ... 其他成员函数将在下文实现 };实操心得将isDirected和isWeighted作为构造参数非常有用。它让我们的图类变得通用。在算法题中你通常能提前知道图的类型用对应的标志初始化即可避免写多个类似的类。3.2 边的添加、删除与查询操作这是图类的核心功能。我们需要仔细处理有向/无向、带权/非带权的区别。// 添加边 (u, v) void addEdge(int u, int v, int weight 1) { if (u 0 || u numVertices || v 0 || v numVertices) { std::cerr Error: Vertex index out of range! std::endl; return; } if (u v) { std::cerr Warning: Self-loop detected. Ignored in simple graph representation. std::endl; return; // 简单图通常不考虑自环可根据需求修改 } matrix[u][v] isWeighted ? weight : 1; // 带权图存权重否则存1 if (!isDirected) { // 如果是无向图矩阵是对称的 matrix[v][u] isWeighted ? weight : 1; } } // 删除边 (u, v) void removeEdge(int u, int v) { if (u 0 || u numVertices || v 0 || v numVertices) { std::cerr Error: Vertex index out of range! std::endl; return; } matrix[u][v] 0; // 设为0表示无边 if (!isDirected) { matrix[v][u] 0; } } // 查询边 (u, v) 是否存在或权重 int getEdge(int u, int v) const { if (u 0 || u numVertices || v 0 || v numVertices) { std::cerr Error: Vertex index out of range! std::endl; return -1; // 或抛异常 } return matrix[u][v]; // 返回0表示无边非0表示有边或权重 } // 判断边是否存在 bool hasEdge(int u, int v) const { return getEdge(u, v) ! 0; }关键点解析下标检查这是必须的防止数组越界导致程序崩溃。在实际项目中可能会用异常替代cerr输出。自环处理在简单图的邻接矩阵表示中对角线元素matrix[i][i]通常没有意义或表示自环。这里选择忽略自环添加。如果你的应用需要自环可以移除这个判断。对称性对于无向图添加或删除边时必须同时操作matrix[u][v]和matrix[v][u]以保持矩阵的对称性。这是最容易出错的地方之一。权重存储我们用一个int矩阵通吃。对于非带权图用1表示有边清晰直观。对于带权图0可能是一个合法的权重比如成本为0的路径这是一个设计缺陷。更严谨的做法是使用std::vectorstd::vectorint*并用nullptr表示无边或者使用一个单独的bool矩阵记录边是否存在。但为了代码简洁和教学清晰本例做了妥协。在解决具体问题时你需要根据权重范围来调整这个“无边”的表示值例如如果权重都是正数可以用-1或INT_MAX表示无边。3.3 图的遍历与信息打印虽然深度优先搜索和广度优先搜索通常作为独立算法实现但作为图类提供一个直观的打印方法来查看结构是非常有用的调试手段。// 打印邻接矩阵 void printMatrix() const { std::cout Adjacency Matrix ( numVertices vertices, (isDirected ? Directed : Undirected) , (isWeighted ? Weighted : Unweighted) ):\n; std::cout ; for (int i 0; i numVertices; i) { std::cout std::setw(3) i; // 设置列宽为3对齐 } std::cout \n; for (int i 0; i numVertices; i) { std::cout std::setw(2) i :; for (int j 0; j numVertices; j) { std::cout std::setw(3) matrix[i][j]; } std::cout \n; } } // 获取顶点数量 int getNumVertices() const { return numVertices; } // 获取所有邻居对于无向图是相连顶点对于有向图是出边邻居 std::vectorint getNeighbors(int v) const { std::vectorint neighbors; for (int i 0; i numVertices; i) { if (matrix[v][i] ! 0) { // 有边 neighbors.push_back(i); } } return neighbors; }printMatrix函数能让你一目了然地看到整个图的连接情况在调试小规模图时极其方便。getNeighbors函数则是为后续实现图遍历算法准备的接口。4. 邻接表实现详解更通用的选择现在来实现更常用、更高效的邻接表。我们将使用C的vector来存储每个顶点的邻居列表因为vector的缓存友好性和易用性通常优于链表。4.1 结构定义与类设计在邻接表中我们需要存储每个邻居顶点以及可能的边权重。因此我们首先定义一个Edge结构体或直接用pair。#include iostream #include vector #include utility // for std::pair // 定义边的结构体存储目标顶点和权重 struct Edge { int to; // 目标顶点 int weight; // 边权重对于非带权图默认为1 Edge(int t, int w 1) : to(t), weight(w) {} }; class AdjacencyListGraph { private: int numVertices; bool isDirected; bool isWeighted; std::vectorstd::vectorEdge adjList; // 邻接表每个顶点对应一个Edge列表 public: // 构造函数 AdjacencyListGraph(int V, bool directed false, bool weighted false) : numVertices(V), isDirected(directed), isWeighted(weighted) { adjList.resize(V); // 初始化V个空的邻居列表 } // ... 其他成员函数 };这里adjList[i]是一个vectorEdge存储了从顶点i出发的所有边。这种设计清晰地将顶点和其关联的边绑定在一起。4.2 边的增删查改实现邻接表的边操作逻辑与矩阵不同主要是在列表中进行查找、插入和删除。// 添加边 (u, v) void addEdge(int u, int v, int weight 1) { if (u 0 || u numVertices || v 0 || v numVertices) { std::cerr Error: Vertex index out of range! std::endl; return; } if (u v) { // 邻接表可以处理自环这里选择添加 adjList[u].push_back(Edge(v, isWeighted ? weight : 1)); return; } adjList[u].push_back(Edge(v, isWeighted ? weight : 1)); if (!isDirected) { // 无向图需要添加反向边 adjList[v].push_back(Edge(u, isWeighted ? weight : 1)); } // 注意邻接表默认允许平行边重复边。如果需要禁止需要在添加前遍历adjList[u]检查是否已存在边(u, v)。 } // 删除边 (u, v) - 效率较低因为需要遍历列表查找 void removeEdge(int u, int v) { if (u 0 || u numVertices || v 0 || v numVertices) { return; } // 删除从u到v的边 for (auto it adjList[u].begin(); it ! adjList[u].end(); it) { if (it-to v) { adjList[u].erase(it); break; // 假设简单图最多一条边 } } if (!isDirected) { // 如果是无向图还要删除从v到u的边 for (auto it adjList[v].begin(); it ! adjList[v].end(); it) { if (it-to u) { adjList[v].erase(it); break; } } } } // 查询边 (u, v) 的权重不存在则返回一个特定值如-1或0 int getEdgeWeight(int u, int v) const { if (u 0 || u numVertices || v 0 || v numVertices) { return -1; // 表示错误或无边 } for (const Edge e : adjList[u]) { if (e.to v) { return e.weight; } } return 0; // 用0表示无边假设权重为正或用-1等 } bool hasEdge(int u, int v) const { return getEdgeWeight(u, v) ! 0; // 根据getEdgeWeight的返回值定义调整 }关键点解析与避坑平行边处理上面的addEdge实现允许平行边即多条相同的(u,v)边。这在某些场景下是需要的比如流量网络中的多条管道。但如果你的算法或问题假设是简单图没有平行边你必须在添加前遍历adjList[u]检查是否已存在到v的边。这是一个常见的面试考点。删除效率在vector中删除中间元素的时间复杂度是O(n)因为需要移动后续元素。如果图需要频繁删边且性能敏感可以考虑使用std::list作为邻接表的底层容器但会牺牲缓存局部性。另一种常见做法是“懒惰删除”即标记边为无效在后续遍历时跳过。查询效率hasEdge和getEdgeWeight需要遍历列表最坏情况O(V)。这是邻接表的主要缺点。如果应用需要频繁的边存在性查询可能需要额外维护一个哈希表来加速。4.3 遍历接口与实用方法邻接表最自然的操作就是遍历某个顶点的所有邻居这恰好是大多数图算法如BFS、DFS、Dijkstra的核心操作。// 获取顶点v的所有出边邻居对于无向图就是所有相邻顶点 const std::vectorEdge getNeighbors(int v) const { // 返回常引用避免拷贝同时防止外部修改内部数据 if (v 0 || v numVertices) { static const std::vectorEdge empty; // 返回一个空向量的引用 return empty; } return adjList[v]; } // 打印邻接表 void printList() const { std::cout Adjacency List ( numVertices vertices, (isDirected ? Directed : Undirected) , (isWeighted ? Weighted : Unweighted) ):\n; for (int i 0; i numVertices; i) { std::cout i : ; for (const Edge e : adjList[i]) { std::cout - ( e.to; if (isWeighted) { std::cout , w: e.weight; } std::cout ) ; } std::cout \n; } } int getNumVertices() const { return numVertices; } bool isGraphDirected() const { return isDirected; } bool isGraphWeighted() const { return isWeighted; }getNeighbors返回一个const引用这是关键的性能优化。图算法中会无数次调用这个函数来获取邻居如果每次返回拷贝当图很大时开销巨大。返回引用避免了拷贝同时用const保证图的结构不会被意外修改。5. 两种实现的对比与性能实测纸上得来终觉浅我们写个简单的测试程序从空间和时间上感受一下两者的差异。#include chrono #include random void testPerformance() { const int V 5000; // 顶点数 const double density 0.01; // 边密度1%的边存在这是一个稀疏图 std::random_device rd; std::mt19937 gen(rd()); std::uniform_int_distribution dis(0, V-1); std::uniform_int_distribution weight_dis(1, 100); // 测试邻接矩阵 auto start std::chrono::high_resolution_clock::now(); AdjacencyMatrixGraph matGraph(V, false, true); long long edgeCount static_castlong long(V * V * density); for (long long i 0; i edgeCount; i) { int u dis(gen); int v dis(gen); int w weight_dis(gen); matGraph.addEdge(u, v, w); } auto end std::chrono::high_resolution_clock::now(); auto duration_mat std::chrono::duration_caststd::chrono::milliseconds(end - start); std::cout Adjacency Matrix build time for edgeCount edges: duration_mat.count() ms std::endl; // 估算内存V*V * sizeof(int) bytes size_t mem_mat V * V * sizeof(int); std::cout Estimated memory: mem_mat / (1024 * 1024) MB std::endl; // 测试邻接表 start std::chrono::high_resolution_clock::now(); AdjacencyListGraph listGraph(V, false, true); for (long long i 0; i edgeCount; i) { int u dis(gen); int v dis(gen); int w weight_dis(gen); listGraph.addEdge(u, v, w); } end std::chrono::high_resolution_clock::now(); auto duration_list std::chrono::duration_caststd::chrono::milliseconds(end - start); std::cout Adjacency List build time for edgeCount edges: duration_list.count() ms std::endl; // 估算内存V * sizeof(vector) 2*E * sizeof(Edge) (无向图每条边存两次) size_t mem_list V * sizeof(std::vectorEdge) 2 * edgeCount * sizeof(Edge); std::cout Estimated memory: mem_list / (1024 * 1024) MB std::endl; // 测试查询性能随机查询10000次 const int queryTimes 10000; start std::chrono::high_resolution_clock::now(); int dummySum 0; // 防止编译器优化掉查询 for (int i 0; i queryTimes; i) { int u dis(gen); int v dis(gen); if (matGraph.hasEdge(u, v)) { dummySum matGraph.getEdge(u, v); } } end std::chrono::high_resolution_clock::now(); auto duration_mat_query std::chrono::duration_caststd::chrono::microseconds(end - start); std::cout Matrix edge query time: duration_mat_query.count() us std::endl; start std::chrono::high_resolution_clock::now(); dummySum 0; for (int i 0; i queryTimes; i) { int u dis(gen); int v dis(gen); if (listGraph.hasEdge(u, v)) { dummySum listGraph.getEdgeWeight(u, v); } } end std::chrono::high_resolution_clock::now(); auto duration_list_query std::chrono::duration_caststd::chrono::microseconds(end - start); std::cout List edge query time: duration_list_query.count() us std::endl; }运行这个测试顶点数5000边密度1%约25万条边你可能会看到类似下面的结果构建时间邻接表可能略慢因为需要多次动态分配内存push_back。内存占用邻接矩阵固定占用约5000*5000*4 bytes ≈ 100MB。而邻接表只存储实际边约2*250000*8 bytes ≈ 4MB假设Edge结构体8字节对齐。内存节省了两个数量级查询时间邻接矩阵的查询是稳定的O(1)极快。邻接表的查询需要遍历列表在稀疏图中平均很快但最坏情况下是O(V)且受缓存影响总体会比矩阵慢。这个测试清晰地印证了之前的理论分析对于稀疏图邻接表在空间上具有压倒性优势而这是大多数实际场景的常态。牺牲一点查询时间换来巨大的空间节省是非常划算的。6. 常见问题与实战排坑指南在实际实现和使用图结构时你会遇到各种各样的问题。下面是我踩过的一些坑和对应的解决方案。6.1 顶点编号从0开始还是从1开始这是一个看似简单却容易引发混乱的问题。C标准库和大多数算法约定数组、vector索引从0开始。因此将顶点编号为0到V-1是最自然、最不容易出错的选择。你上面看到的代码都是基于0起始的。问题输入习惯很多算法题或教科书示例的输入顶点编号是从1开始的。解决方案在读取输入后立即将所有顶点编号减1转换为0起始的内部表示。在输出结果时再加1转换回去。永远在内部使用0起始编号这能避免大量的下标计算错误。可以在图类构造函数或addEdge方法中封装这个转换逻辑。6.2 如何高效判断边是否存在针对邻接表邻接表的hasEdge是O(degree)操作如果频繁调用比如在某些特定算法中会成为瓶颈。方案一使用unordered_set存储邻居。将adjList的类型从vectorEdge改为vectorunordered_setint或vectorunordered_mapint, int后者同时存储权重。这样hasEdge和getEdgeWeight可以降到平均O(1)。但代价是遍历所有邻居时这是更常见的操作的常数时间变大且内存开销增加。方案二空间换时间维护一个矩阵副本。对于需要频繁边查询但又想用邻接表遍历的场景可以同时维护一个vectorvectorbool的hasEdge矩阵。但这几乎等同于邻接矩阵的空间开销。方案三算法优化。很多时候你并不需要频繁的随机边查询。标准的BFS/DFS/Dijkstra等算法核心操作是“获取顶点v的所有邻居并处理”这正是邻接表的强项。重新审视你的算法看是否真的需要那么多hasEdge调用。6.3 处理大规模图时的内存优化技巧当顶点数超过10万即使使用邻接表内存也可能紧张。使用vectorint压缩存储如果不带权重每个邻居只存目标顶点int。如果带权重可以使用vectorpairint, int或者两个vector一个存目标顶点一个存权重。pair和struct Edge相比可能节省一些内存对齐带来的开销。使用前向星这是一种用两个大数组head,edges模拟邻接表的方法常见于ACM竞赛中内存使用非常紧凑且遍历效率高。但对于动态增删边不友好。考虑使用uint32_t而非int如果顶点数小于2^32使用uint32_t可以节省一半内存在64位系统上int通常是4字节但结构体对齐可能占用8字节。使用内存池如果图结构固定可以使用自定义分配器来减少vector动态扩容和内存碎片。6.4 邻接表遍历中的迭代器失效问题这是一个经典的C STL陷阱。当你在遍历某个顶点的邻居列表adjList[v]时如果遍历过程中修改了这个列表比如删除了一条边可能会导致迭代器失效程序崩溃。// 错误示例遍历时删除满足条件的边 for (auto it adjList[v].begin(); it ! adjList[v].end(); it) { if (someCondition(*it)) { adjList[v].erase(it); // 删除后it失效后续it行为未定义 } } // 正确写法使用erase-remove惯用法或后向遍历 auto vec adjList[v]; vec.erase(std::remove_if(vec.begin(), vec.end(), [](const Edge e) { return someCondition(e); }), vec.end()); // 或者如果必须用循环且只删除一个元素可以这样效率较低 for (auto it adjList[v].begin(); it ! adjList[v].end(); ) { if (someCondition(*it)) { it adjList[v].erase(it); // erase返回下一个有效迭代器 } else { it; } }在编写图算法时尤其是涉及修改图结构的算法如最小生成树的Kruskal算法需要删边不通常不直接删但类似场景一定要警惕迭代器失效。6.5 如何为图算法提供统一的接口你可能会实现多种图算法BFS, DFS, Dijkstra, Prim等。一个好的设计是让这些算法接收一个“图接口”作为参数而不是具体的AdjacencyListGraph或AdjacencyMatrixGraph类。这需要用到抽象基类接口类。class Graph { public: virtual ~Graph() default; virtual int getNumVertices() const 0; virtual const std::vectorEdge getNeighbors(int v) const 0; virtual bool hasEdge(int u, int v) const 0; virtual int getEdgeWeight(int u, int v) const 0; // ... 其他必要接口 }; // 让AdjacencyListGraph和AdjacencyMatrixGraph都继承自Graph并实现这些虚函数。这样你的dijkstra(Graph g, int source)函数就可以处理任何实现了Graph接口的图类大大提高了代码的复用性和可测试性。这是面向对象设计在数据结构中的应用在大型项目中非常有用。