1. 项目概述为什么图是数据结构中的“瑞士军刀”在数据结构的世界里我们学过线性的数组、链表也接触过分层的树和堆。但当我们面对社交网络的好友关系、地图导航的路径规划、或是编译器分析代码的依赖关系时这些结构就显得力不从心了。这时图Graph就该登场了。它就像数据结构工具箱里的“瑞士军刀”虽然结构相对复杂但能优雅地建模现实世界中无处不在的“多对多”关系。简单说图就是由顶点Vertex和连接顶点的边Edge组成的集合。顶点代表实体比如城市、用户、网页边代表实体间的关系比如道路、关注、超链接。这次我们不只停留在书本上的定义而是直接动手用C从零实现一个图结构。你会看到两种最经典的实现方式邻接矩阵和邻接表并附上完整的、可运行的源代码。无论你是正在备战期末考试的学生还是准备技术面试的求职者亦或是想夯实基础的开发者通过这个“造轮子”的过程你都能透彻理解图的存储、遍历以及其背后的设计哲学。理解图是迈向算法世界更深处——如图论、网络流、图神经网络——不可或缺的第一步。2. 核心概念与设计思路拆解在写代码之前我们必须把图的基本概念和设计选择搞清楚。这决定了我们代码的骨架和效率。2.1 图的分类与核心术语图可以根据边的特性分为好几类不同的类型直接影响到我们实现时的数据结构选择。无向图 vs 有向图这是最基础的分类。无向图的边没有方向就像微信好友关系我们是好友你也是我的好友。有向图的边有方向就像微博的关注关系我关注了你但你不一定关注我。在代码中无向图的一条边需要在两个方向上都做记录。带权图 vs 无权图边是否可以携带一个数值权重。地图中道路的长度、网络传输的带宽成本都是权重的例子。实现时我们需要一个额外的变量来存储这个权重。连通图图中任意两个顶点之间都存在路径。这个性质对很多算法如最小生成树至关重要。度对于顶点来说度是与它相关联的边的数量。在有向图中还要细分为入度指向该顶点的边数和出度从该顶点指出的边数。计算顶点的度是图的基本操作之一。理解了这些我们就能明确我们要实现的目标一个能够灵活表示无向/有向、带权/无权图的通用结构。2.2 邻接矩阵与邻接表的抉择如何用计算机的内存来表示顶点和边的关系主流有两种方案它们各有优劣适用场景截然不同。邻接矩阵用一个二维数组矩阵matrix来表示。如果图有V个顶点那么矩阵就是V x V的大小。matrix[i][j]的值表示顶点i到顶点j的边的情况。对于无权图可以用0表示无边1表示有边对于带权图则直接存储权重值可以用一个特殊值如INT_MAX表示无边。优点实现极其简单直观检查任意两个顶点间是否存在边速度是O(1)适合表示稠密图边数接近顶点数平方。缺点空间复杂度是O(V²)对于顶点数很多但边数很少的稀疏图如社交网络空间浪费巨大遍历一个顶点的所有邻居需要O(V)时间即使它只有几个邻居。邻接表为每个顶点维护一个列表可以是数组、链表、向量里面存储的是与该顶点直接相连的所有邻居顶点对于带权图还需存储权重。本质上它是“数组链表”或“数组动态数组”的结构。优点空间复杂度是O(V E)与顶点数和边数成正比非常适合稀疏图节省大量内存遍历一个顶点的所有邻居非常高效时间复杂度等于该顶点的度。缺点检查任意两个顶点i和j之间是否有边需要遍历i的邻居列表最坏情况O(V)实现上比邻接矩阵稍复杂。设计心得选择哪种实现没有绝对的对错只有合不合适。如果你的图边非常密集或者需要频繁进行“两点是否相连”的查询邻接矩阵是更好的选择。如果你的图是典型的社交网络、网页链接图顶点动辄百万千万边却相对稀疏那么邻接表几乎是唯一可行的选择。在算法竞赛和日常开发中邻接表的使用频率远高于邻接矩阵。3. C实现详解从类设计到核心操作接下来我们进入实战环节。我将分别用邻接矩阵和邻接表实现一个通用的、支持带权有向/无向图的Graph类。为了清晰和实用我们采用面向对象的设计并利用C STL来简化开发。3.1 基于邻接矩阵的实现我们首先定义一个GraphMatrix类。它的核心是一个二维向量vectorvectorint用来存储边的权重。#include iostream #include vector #include queue #include stack #include climits // 用于INT_MAX using namespace std; class GraphMatrix { private: int numVertices; // 顶点数量 bool isDirected; // 是否为有向图 vectorvectorint adjMatrix; // 邻接矩阵 public: // 构造函数初始化一个指定顶点数、是否有向的图 GraphMatrix(int vertices, bool directed false) : numVertices(vertices), isDirected(directed) { // 初始化矩阵所有边初始化为INT_MAX表示无边 adjMatrix.resize(numVertices, vectorint(numVertices, INT_MAX)); // 顶点到自身的距离通常设为0这里根据需求我们保持INT_MAX表示没有自环边 // for (int i 0; i numVertices; i) { // adjMatrix[i][i] 0; // } } // 添加边无权图 void addEdge(int src, int dest) { addEdge(src, dest, 1); // 默认权重为1 } // 添加边带权图- 核心方法 void addEdge(int src, int dest, int weight) { if (src 0 || src numVertices || dest 0 || dest numVertices) { cerr 错误顶点索引越界 endl; return; } adjMatrix[src][dest] weight; if (!isDirected) { // 如果是无向图对称位置也要添加 adjMatrix[dest][src] weight; } } // 打印邻接矩阵 void printGraph() const { cout 邻接矩阵表示 endl; for (int i 0; i numVertices; i) { for (int j 0; j numVertices; j) { if (adjMatrix[i][j] INT_MAX) { cout INF\t; } else { cout adjMatrix[i][j] \t; } } cout endl; } } // 获取顶点数 int getNumVertices() const { return numVertices; } // 获取邻接矩阵只读 const vectorvectorint getAdjMatrix() const { return adjMatrix; } };代码解析与注意事项权重表示我们用INT_MAX来代表“无边”。这在图算法中很常见比如在Dijkstra最短路径算法中初始化距离数组就常用INT_MAX表示无穷远。如果你确定权重都是正数这很安全。无向图的处理在addEdge函数中我们通过isDirected标志位来判断。如果是无向图我们需要同时设置adjMatrix[src][dest]和adjMatrix[dest][src]。这是保证图无向性的关键。空间开销注意adjMatrix的大小是V x V。即使我们只添加了少数几条边这个二维数组也已经完全分配好了。这就是邻接矩阵在稀疏图上的主要缺点。顶点索引我们约定顶点用从0开始的连续整数编号。这是最方便的实现方式。如果实际应用中的顶点是字符串或其他类型通常需要先用一个映射如unordered_mapstring, int将其转换为整数索引。3.2 基于邻接表的实现邻接表的实现更灵活也更常用。我们为每个顶点存储一个列表列表中的元素是一个pair包含邻居顶点和边的权重。class GraphList { private: int numVertices; bool isDirected; // 邻接表每个顶点对应一个向量向量中存储 (邻居顶点, 权重) 对 vectorvectorpairint, int adjList; public: GraphList(int vertices, bool directed false) : numVertices(vertices), isDirected(directed) { adjList.resize(numVertices); } // 添加边无权图 void addEdge(int src, int dest) { addEdge(src, dest, 1); } // 添加边带权图- 核心方法 void addEdge(int src, int dest, int weight) { if (src 0 || src numVertices || dest 0 || dest numVertices) { cerr 错误顶点索引越界 endl; return; } adjList[src].push_back({dest, weight}); if (!isDirected) { // 无向图需要添加反向边 adjList[dest].push_back({src, weight}); } } // 打印邻接表 void printGraph() const { cout 邻接表表示 endl; for (int i 0; i numVertices; i) { cout 顶点 i - ; for (const auto neighbor : adjList[i]) { cout ( neighbor.first , neighbor.second ) ; } cout endl; } } // 获取顶点数 int getNumVertices() const { return numVertices; } // 获取邻接表只读 const vectorvectorpairint, int getAdjList() const { return adjList; } };代码解析与实操要点数据结构选择我们使用vectorvectorpairint, int作为邻接表。外层vector的索引对应顶点编号。内层vector存储该顶点的所有出边。pairint, int的第一个元素是目标顶点dest第二个元素是权重weight。使用vector而非list是因为vector的缓存友好性在遍历时通常能带来更好的性能且内存开销更小。动态增长与邻接矩阵一次性分配所有空间不同邻接表的内存是随着边的添加而动态增长的。adjList[src]这个向量只有在添加以src为起点的边时才会被push_back。这完美契合了稀疏图的特性。遍历邻居要获取顶点i的所有邻居只需遍历adjList[i]这个向量即可。时间复杂度是O(degree(i))即与该顶点直接相连的边数非常高效。查询边存在如果想查询边(i, j)是否存在就需要遍历adjList[i]检查其中是否有first等于j的pair。最坏情况是O(degree(i))。如果这个操作非常频繁可以考虑将内层的vector换成unordered_set如果无权或unordered_map如果带权将查询时间降到平均O(1)但会牺牲一些遍历性能和内存。4. 图的遍历算法实现与应用存储结构搭建好了接下来就要让图“动”起来。遍历是图算法的基础如同树的先序、中序遍历一样。图的两种基本遍历是广度优先搜索BFS和深度优先搜索DFS。它们能解决“从某点出发能到达哪些点”、“图中是否有环”、“计算连通分量”等问题。4.1 广度优先搜索BFS实现BFS的思想是“层层推进”。它从起点开始先访问所有直接邻居再访问邻居的邻居以此类推。这天然适合用队列FIFO来实现。BFS常用来求无权图的最短路径因为每层距离起点都增加1。// 作为GraphList的成员函数添加 void BFS(int startVertex) const { vectorbool visited(numVertices, false); // 访问标记数组 queueint q; visited[startVertex] true; q.push(startVertex); cout BFS遍历顺序从顶点 startVertex 开始: ; while (!q.empty()) { int current q.front(); q.pop(); cout current ; // 访问当前顶点 // 遍历当前顶点的所有邻居 for (const auto neighbor : adjList[current]) { int adjVertex neighbor.first; if (!visited[adjVertex]) { visited[adjVertex] true; q.push(adjVertex); } } } cout endl; }BFS关键点队列的作用队列保证了“先被发现的顶点先被访问”这正是“广度优先”的含义。visited数组这是图遍历与树遍历最大的不同。图可能有环一个顶点可能通过多条路径被访问到。visited数组防止了程序陷入无限循环和重复访问。时间复杂度每个顶点入队、出队一次每条边被检查一次在邻接表中检查发生在遍历邻居列表时。因此BFS的时间复杂度是O(V E)其中V是顶点数E是边数。这是一个非常高效的算法。4.2 深度优先搜索DFS实现DFS的思想是“一条路走到黑再回头”。它从起点开始沿着一条边不断深入直到无法继续然后回溯到上一个顶点尝试另一条路径。这可以用递归系统栈或显式栈来实现。DFS适合拓扑排序、寻找连通分量、检测环等。递归版本最简洁// 作为GraphList的成员函数添加 void DFSRecursive(int startVertex) const { vectorbool visited(numVertices, false); cout DFS遍历顺序递归从顶点 startVertex 开始: ; DFSUtil(startVertex, visited); cout endl; } private: // 递归辅助函数 void DFSUtil(int vertex, vectorbool visited) const { visited[vertex] true; cout vertex ; for (const auto neighbor : adjList[vertex]) { int adjVertex neighbor.first; if (!visited[adjVertex]) { DFSUtil(adjVertex, visited); } } }迭代版本使用栈// 作为GraphList的成员函数添加 void DFSIterative(int startVertex) const { vectorbool visited(numVertices, false); stackint s; s.push(startVertex); // 注意迭代版本中顶点在出栈时才被标记为访问和输出 // 另一种写法是在入栈时标记取决于具体应用 cout DFS遍历顺序迭代从顶点 startVertex 开始: ; while (!s.empty()) { int current s.top(); s.pop(); if (!visited[current]) { visited[current] true; cout current ; } // 将未访问的邻居逆序入栈以保证与递归版本顺序类似先访问第一个邻居 // 注意vector遍历是顺序的入栈后顺序会反转 for (auto it adjList[current].rbegin(); it ! adjList[current].rend(); it) { int adjVertex it-first; if (!visited[adjVertex]) { s.push(adjVertex); } } } cout endl; }DFS关键点与避坑指南递归深度递归实现非常简洁但对于顶点数非常多例如上万的图递归调用栈可能很深有栈溢出的风险。对于大规模图迭代版本更安全。访问时机在迭代版本中一个顶点可能被多次压入栈中通过不同的路径。因此必须在顶点出栈时检查visited标记而不是在入栈时标记。如果在入栈时标记可能会漏掉一些通过更短路径到达该顶点的可能性在DFS中这通常不影响遍历完整性但逻辑上不严谨。而在BFS的队列中由于队列的FIFO特性在入队时标记是安全的。遍历顺序DFS的遍历顺序不是唯一的它取决于你处理邻居的顺序即adjList中边的存储顺序。上述迭代版本通过反向迭代器入栈试图模拟递归版本的顺序但这并非强制要求。时间复杂度与BFS相同也是O(V E)。每个顶点被访问一次每条边被检查一次。5. 完整测试用例与常见问题排查理论结合实践我们写一个main函数来测试上述所有的类和方法并讨论一些实际编码中容易遇到的问题。int main() { cout 测试邻接矩阵图 endl; // 创建一个无向、带权图有5个顶点 GraphMatrix gm(5, false); gm.addEdge(0, 1, 2); gm.addEdge(0, 4, 8); gm.addEdge(1, 2, 3); gm.addEdge(1, 3, 5); gm.addEdge(2, 3, 1); gm.addEdge(3, 4, 4); gm.printGraph(); cout \n 测试邻接表图 endl; // 创建一个有向、无权图有5个顶点 GraphList gl(5, true); gl.addEdge(0, 1); gl.addEdge(0, 4); gl.addEdge(1, 2); gl.addEdge(1, 3); gl.addEdge(2, 3); gl.addEdge(3, 4); gl.printGraph(); cout \n 测试图的遍历 endl; // 测试BFS和DFS GraphList gl2(6, false); // 无向无权图用于遍历 gl2.addEdge(0, 1); gl2.addEdge(0, 2); gl2.addEdge(1, 3); gl2.addEdge(1, 4); gl2.addEdge(2, 5); gl2.addEdge(3, 4); cout 图结构 endl; gl2.printGraph(); gl2.BFS(0); gl2.DFSRecursive(0); gl2.DFSIterative(0); return 0; }运行这段代码你可以直观地看到两种存储方式的差异以及BFS和DFS遍历顺序的不同。5.1 常见问题与调试技巧实录在实际实现和使用图的过程中你肯定会遇到各种问题。下面是我总结的一些“坑”和解决思路顶点索引越界这是最常见的运行时错误。我们的实现假设顶点编号是从0到V-1的连续整数。在addEdge或遍历时如果传入的顶点编号 V就会访问非法内存。排查在addEdge函数开头添加边界检查如我们代码中所做。在从外部如文件读入图数据时要确保数据规范。扩展如果想支持非连续或字符串类型的顶点可以在类内部维护一个unordered_mapT, int的映射将顶点标识符映射到内部连续的整数索引。所有内部操作都使用整数索引对外接口再转换回来。忘记处理无向图的双向边在addEdge时如果图是无向的必须添加两条有向边(src, dest)和(dest, src)。这是一个非常容易遗漏的逻辑错误会导致图的性质完全错误。检查打印出图的邻接矩阵或邻接表检查无向图是否对称邻接矩阵或每条边是否成对出现邻接表。遍历时陷入死循环忘记使用visited数组或者在迭代DFS中错误地设置visited标记的时机都可能导致程序在环中无限循环。调试在遍历循环中加入简单的打印语句输出当前正在访问的顶点和栈/队列的状态。观察是否某个顶点被重复访问。权重初始化的陷阱在邻接矩阵中我们用INT_MAX表示“无边”。但在一些算法中如果权重相加可能导致溢出INT_MAX 正数。在实现像Floyd-Warshall或使用松弛操作的算法时需要特别小心有时会用0x3f3f3f3f这样一个较大的、但相加不会溢出的数来代替INT_MAX。性能问题对于超大规模的图百万顶点以上即使是邻接表使用vectorvectorpairint, int也可能因为内存不连续和动态扩容带来开销。在性能要求极高的场景如高性能图计算可能需要自己管理内存使用扁平化的数组如CSR格式来存储邻接表但这会大大增加代码复杂度。选择邻接表的内层容器我们用了vector。在需要频繁删除边的场景下list可能更合适。在需要频繁判断边是否存在的场景下unordered_set或unordered_map更合适。没有最好的只有最适合当前操作的。理解并实现了图的基本存储和遍历你就已经掌握了图论算法的基石。在此基础上你可以进一步探索最短路径算法Dijkstra, Bellman-Ford, Floyd、最小生成树算法Prim, Kruskal、拓扑排序、强连通分量Kosaraju, Tarjan等更高级的主题。每一个高级算法都离不开对图这种结构的深刻理解和我们上面实现的基本操作。