1. 从“图”谈起为什么它不只是点和线如果你学过链表、栈、队列可能会觉得数据结构就是一条线或者一个先进后出的盒子。但当你第一次接触“图”时那种感觉是完全不同的。它不再是简单的线性或层级关系而是一张网一个可以描述万物的关系模型。我刚开始学图的时候总觉得它抽象离实际编程很远。直到后来我需要为一个社交网络功能设计“可能认识的人”推荐或者为一个物流系统规划最短配送路径时我才恍然大悟图其实就藏在这些最真实、最复杂的业务场景背后。所谓图Graph就是由顶点Vertex和连接这些顶点的边Edge组成的数据结构。顶点代表实体比如一个人、一个城市、一个网页边代表实体之间的关系比如好友关系、道路、超链接。这种结构天生就是为了刻画“多对多”的复杂关系。与链表的一对一、树的一对多相比图的表达能力是最强的这也意味着它的操作和算法更为丰富和挑战。今天我们不谈高深的图算法就扎扎实实地聊聊图的基本操作实现。这些操作是构建一切图算法的基础就像盖房子前要先学会砌砖。我们会从最基础的“如何表示一张图”开始一步步实现增加顶点、增加边、查找、遍历等核心操作。我会用C语言来描述因为指针和结构体能让你最清晰地看到内存中图的“骨架”但其中的思想是语言无关的。无论你用Java、Python还是C理解了本质迁移起来轻而易举。2. 图的两种灵魂邻接矩阵与邻接表在动手写代码之前我们必须做出一个最重要的设计决策如何在计算机内存中表示一张图这直接决定了后续所有操作的效率和适用场景。主流有两种表示方法邻接矩阵和邻接表。它们没有绝对的好坏只有是否适合。2.1 邻接矩阵直观的“城市地图”想象一个N个城市的交通图。邻接矩阵就像一个N行N列的表格二维数组。如果城市i到城市j有直达道路就在表格的第i行第j列标记为1或道路的权重如距离如果没有就标记为0或一个特殊值如无穷大。C语言结构定义示例#define MAX_VERTEX 100 // 预设最大顶点数 #define INFINITY 65535 // 用一个极大数表示“无穷远”即无边 typedef struct { char vexs[MAX_VERTEX]; // 顶点数组用于存储顶点信息如名称 int arcs[MAX_VERTEX][MAX_VERTEX]; // 邻接矩阵边表 int numVertexes, numEdges; // 图的当前顶点数和边数 } MGraph;初始化一个无向图void CreateMGraph(MGraph *G) { int i, j, k, w; printf(输入顶点数和边数:\n); scanf(%d %d, G-numVertexes, G-numEdges); // 读入顶点信息 for(i 0; i G-numVertexes; i) { printf(输入第%d个顶点信息: , i1); scanf( %c, G-vexs[i]); // 假设顶点用字符表示 } // 初始化邻接矩阵 for(i 0; i G-numVertexes; i) { for(j 0; j G-numVertexes; j) { if(i j) G-arcs[i][j] 0; // 自己到自己的距离为0 else G-arcs[i][j] INFINITY; // 初始化为无穷大表示无边 } } // 读入边信息建立邻接矩阵 for(k 0; k G-numEdges; k) { printf(输入边(vi, vj)的下标i、j和权值w:\n); scanf(%d %d %d, i, j, w); G-arcs[i][j] w; G-arcs[j][i] w; // 因为是无向图矩阵是对称的 } }邻接矩阵的优劣分析优点直观易懂检查任意两个顶点间是否有边时间复杂度是O(1)直接数组下标访问。方便计算顶点的度对于无向图行或列非零元素个数对于有向图出度是行非零个数入度是列非零个数。非常适合表示稠密图边数接近顶点数平方因为矩阵本身占据了O(V²)空间边多也不会显著增加开销。缺点空间浪费严重对于稀疏图边数远小于顶点数平方矩阵中大部分都是0或INFINITY浪费了大量空间。添加/删除顶点麻烦需要动态调整二维数组大小成本高。通常需要预设一个足够大的MAX_VERTEX。提示在项目初期如果图规模固定且比较稠密或者需要频繁判断任意两点间关系邻接矩阵是简单可靠的选择。2.2 邻接表灵活的“通讯录”邻接表更像是一个“数组链表”的组合。数组部分存放所有顶点每个顶点后面跟着一个链表链表中存储所有与该顶点直接相连的邻居顶点及边的信息。C语言结构定义示例// 边表结点 typedef struct EdgeNode { int adjvex; // 邻接点域存储该顶点对应的下标 int weight; // 用于存储权值非网图可以不需要 struct EdgeNode *next; // 链域指向下一个邻接点 } EdgeNode; // 顶点表结点 typedef struct VertexNode { char data; // 顶点信息 EdgeNode *firstedge; // 边表头指针 } VertexNode, AdjList[MAX_VERTEX]; // 图结构 typedef struct { AdjList adjList; int numVertexes, numEdges; // 图的当前顶点数和边数 } GraphAdjList;初始化一个无向图的邻接表void CreateALGraph(GraphAdjList *G) { int i, j, k; EdgeNode *e; printf(输入顶点数和边数:\n); scanf(%d %d, G-numVertexes, G-numEdges); // 读入顶点信息建立顶点表 for(i 0; i G-numVertexes; i) { printf(输入第%d个顶点信息: , i1); scanf( %c, G-adjList[i].data); G-adjList[i].firstedge NULL; // 将边表置为空表 } // 建立边表头插法更简单 for(k 0; k G-numEdges; k) { printf(输入边(vi, vj)的顶点序号:\n); scanf(%d %d, i, j); // 为边(i, j)生成边表结点头插法插入顶点i的链表 e (EdgeNode*)malloc(sizeof(EdgeNode)); e-adjvex j; e-next G-adjList[i].firstedge; G-adjList[i].firstedge e; // 因为是无向图还需对称地插入边(j, i) e (EdgeNode*)malloc(sizeof(EdgeNode)); e-adjvex i; e-next G-adjList[j].firstedge; G-adjList[j].firstedge e; } }邻接表的优劣分析优点节省空间只存储实际存在的边对于稀疏图空间复杂度为O(VE)远优于邻接矩阵。添加顶点灵活只需在数组末尾添加并初始化其边链表即可。能高效地遍历一个顶点的所有邻接点这对于BFS/DFS等遍历算法至关重要。缺点判断任意两顶点间是否有边效率较低需要遍历其中一个顶点的链表时间复杂度为O(度)。对有向图求入度不方便需要遍历整个邻接表或额外维护一个逆邻接表。链表结构带来的内存开销指针和缓存不友好问题。注意在实际工程中除非图非常小且稠密否则邻接表通常是更通用的选择。现代编程语言中如C的vectorlistintPython的字典嵌套列表都能很方便地实现邻接表。3. 核心操作实现从建图到遍历有了图的表示方法我们就可以实现一系列基本操作了。我们以邻接表为例进行实现因为它更常用、更灵活。3.1 顶点与边的增删查改这些是维护图结构的基础。1. 查找顶点根据顶点数据如名称查找其索引位置。这是很多其他操作的前提。// 在顶点表中查找值为ch的顶点返回其下标未找到返回-1 int LocateVex(GraphAdjList *G, char ch) { for(int i 0; i G-numVertexes; i) { if(G-adjList[i].data ch) { return i; } } return -1; }2. 增加顶点在顶点数组末尾添加一个新顶点并初始化其边链表。// 向图G中添加一个数据为ch的新顶点 int AddVertex(GraphAdjList *G, char ch) { if(G-numVertexes MAX_VERTEX) { printf(顶点数已达上限无法添加\n); return -1; } if(LocateVex(G, ch) ! -1) { printf(顶点已存在\n); return -1; } G-adjList[G-numVertexes].data ch; G-adjList[G-numVertexes].firstedge NULL; G-numVertexes; printf(顶点 %c 添加成功索引为 %d。\n, ch, G-numVertexes-1); return G-numVertexes - 1; // 返回新顶点的索引 }3. 增加边在指定的两个顶点之间添加一条边。需要处理无向图的双向添加。// 在顶点v1和v2之间添加一条边无向图 int AddEdge(GraphAdjList *G, char v1, char v2) { int i LocateVex(G, v1); int j LocateVex(G, v2); if(i -1 || j -1) { printf(顶点不存在\n); return 0; } // 检查边是否已存在避免重复 EdgeNode *p G-adjList[i].firstedge; while(p ! NULL) { if(p-adjvex j) { printf(边(%c, %c)已存在\n, v1, v2); return 0; } p p-next; } // 使用头插法插入边(i, j) EdgeNode *e (EdgeNode*)malloc(sizeof(EdgeNode)); e-adjvex j; e-next G-adjList[i].firstedge; G-adjList[i].firstedge e; // 无向图对称插入边(j, i) e (EdgeNode*)malloc(sizeof(EdgeNode)); e-adjvex i; e-next G-adjList[j].firstedge; G-adjList[j].firstedge e; G-numEdges; printf(边(%c, %c)添加成功。\n, v1, v2); return 1; }4. 删除边删除两个顶点之间的边。需要找到边表节点并正确维护链表。// 删除顶点v1和v2之间的边无向图 int DeleteEdge(GraphAdjList *G, char v1, char v2) { int i LocateVex(G, v1); int j LocateVex(G, v2); if(i -1 || j -1) { printf(顶点不存在\n); return 0; } int success 0; // 从顶点i的链表中删除指向j的边 EdgeNode *p G-adjList[i].firstedge; EdgeNode *pre NULL; while(p ! NULL) { if(p-adjvex j) { if(pre NULL) { // 要删除的是头节点 G-adjList[i].firstedge p-next; } else { pre-next p-next; } free(p); success 1; break; } pre p; p p-next; } // 从顶点j的链表中删除指向i的边 p G-adjList[j].firstedge; pre NULL; while(p ! NULL) { if(p-adjvex i) { if(pre NULL) { G-adjList[j].firstedge p-next; } else { pre-next p-next; } free(p); success 1; // 确保两边都删除成功 break; } pre p; p p-next; } if(success) { G-numEdges--; printf(边(%c, %c)删除成功。\n, v1, v2); } else { printf(边(%c, %c)不存在\n, v1, v2); } return success; }5. 删除顶点进阶操作这是最复杂的操作因为删除一个顶点需要删除所有与之相连的边。// 删除顶点ch及其所有关联的边 int DeleteVertex(GraphAdjList *G, char ch) { int v LocateVex(G, ch); if(v -1) { printf(顶点不存在\n); return 0; } // 1. 删除所有以ch为终点的边即其他顶点链表中指向ch的边 for(int i 0; i G-numVertexes; i) { if(i v) continue; // 跳过自己 DeleteEdge(G, G-adjList[i].data, ch); // 复用删边函数 } // 2. 释放顶点ch自身的边链表所有以ch为起点的边 EdgeNode *p G-adjList[v].firstedge; while(p ! NULL) { EdgeNode *temp p; p p-next; free(temp); } G-adjList[v].firstedge NULL; // 3. 将顶点数组中最后一个顶点移动到被删除的位置以保持数组紧凑 G-adjList[v] G-adjList[G-numVertexes - 1]; // 4. 非常重要更新所有边表中原来指向最后一个顶点的指针让其指向新的位置v for(int i 0; i G-numVertexes; i) { p G-adjList[i].firstedge; while(p ! NULL) { if(p-adjvex G-numVertexes - 1) { p-adjvex v; // 重定向 } p p-next; } } G-numVertexes--; printf(顶点 %c 及其所有边已删除。\n, ch); return 1; }实操心得删除顶点是图操作中最易出错的部分。关键在于两步一是清理所有关联边二是用末尾顶点填补空缺后必须更新整个图中所有指向原末尾顶点的引用。忘记第二步会导致“野指针”访问到错误或已释放的内存。3.2 图的遍历深度优先与广度优先遍历是图算法的基石目的是系统地访问图中每一个顶点且仅访问一次。两种最经典的策略是深度优先搜索DFS和广度优先搜索BFS。1. 深度优先搜索DFS—— “一条路走到黑”DFS类似于树的先序遍历。它从某个顶点出发沿着一条路径不断深入直到尽头然后回溯探索其他分支。递归实现非常直观。// 访问标志数组防止重复访问 int visited[MAX_VERTEX]; // 对邻接表表示的图G进行深度优先遍历 void DFS(GraphAdjList *G, int i) { EdgeNode *p; visited[i] 1; // 标记当前顶点已访问 printf(%c , G-adjList[i].data); // 打印或处理顶点 p G-adjList[i].firstedge; while(p ! NULL) { if(!visited[p-adjvex]) { // 对未访问的邻接顶点递归调用 DFS(G, p-adjvex); } p p-next; } } // DFS遍历入口处理非连通图 void DFSTraverse(GraphAdjList *G) { int i; for(i 0; i G-numVertexes; i) { visited[i] 0; // 初始化所有顶点为未访问 } printf(深度优先遍历结果: ); for(i 0; i G-numVertexes; i) { if(!visited[i]) { DFS(G, i); // 对未访问过的顶点调用DFS } } printf(\n); }DFS的非递归实现使用栈递归虽然简洁但在图很大时可能导致栈溢出。非递归版本用栈模拟递归过程。void DFS_NonRecursive(GraphAdjList *G, int start) { int stack[MAX_VERTEX], top -1; int visited[MAX_VERTEX] {0}; EdgeNode *p; printf(DFS非递归遍历: ); // 起始顶点入栈并访问 stack[top] start; visited[start] 1; printf(%c , G-adjList[start].data); while(top ! -1) { int v stack[top]; // 获取栈顶但不弹出 p G-adjList[v].firstedge; // 寻找v的一个未访问的邻接点 while(p ! NULL) { if(!visited[p-adjvex]) { // 找到访问并入栈 printf(%c , G-adjList[p-adjvex].data); visited[p-adjvex] 1; stack[top] p-adjvex; break; // 跳出内层while继续从这个新顶点深入 } p p-next; } if(p NULL) { // v的所有邻接点都已访问回溯 top--; } } printf(\n); }2. 广度优先搜索BFS—— “层层推进”BFS类似于树的层序遍历。它从起始顶点开始先访问所有直接邻居然后再访问邻居的邻居以此类推。这天然需要队列Queue的支持。// 简单循环队列实现 int queue[MAX_VERTEX]; int front 0, rear 0; void BFS(GraphAdjList *G, int start) { int visited[MAX_VERTEX] {0}; EdgeNode *p; printf(广度优先遍历结果: ); // 起始顶点入队并访问 printf(%c , G-adjList[start].data); visited[start] 1; queue[rear] start; // 入队 while(front ! rear) { int v queue[front]; // 出队 p G-adjList[v].firstedge; while(p ! NULL) { if(!visited[p-adjvex]) { // 访问邻接点并入队 printf(%c , G-adjList[p-adjvex].data); visited[p-adjvex] 1; queue[rear] p-adjvex; } p p-next; } } printf(\n); }DFS与BFS的核心区别与应用场景特性深度优先搜索 (DFS)广度优先搜索 (BFS)数据结构栈 (递归或显式栈)队列遍历顺序纵向深入回溯探索横向扩散层层推进空间复杂度O(h)h为递归深度/图的最大深度O(w)w为图的最大宽度经典应用拓扑排序、连通分量检测、寻找路径不一定最短、解决迷宫问题最短路径无权图、广播网络、社交网络中的“好友推荐”注意对于非连通图一次DFS或BFS只能遍历一个连通分量。因此遍历入口函数需要检查所有顶点对未访问的顶点再次发起遍历以确保访问到所有顶点。4. 从理论到实战一个简单社交关系模拟理解了基本操作我们用一个综合例子把它们串起来。假设我们要模拟一个极简的社交网络用户可以添加好友无向边我们可以查找两个人的最短认识路径通过多少中间人。问题简化在无权图中两人之间的最短认识路径就是边数最少的路径。这正好是BFS的用武之地因为BFS按层遍历第一次到达目标顶点时所经过的层数就是最短路径长度。实现思路用邻接表存储用户顶点和好友关系边。使用BFS搜索从用户A到用户B的路径。在BFS过程中需要记录每个顶点的前驱顶点是谁发现它的以便最后回溯出完整路径。C语言实现代码// 查找从start到target的最短路径无权图 void BFS_ShortestPath(GraphAdjList *G, char start, char target) { int s LocateVex(G, start); int t LocateVex(G, target); if(s -1 || t -1) { printf(用户不存在\n); return; } if(s t) { printf(起始用户和目标用户是同一人。\n); return; } int visited[MAX_VERTEX] {0}; int predecessor[MAX_VERTEX]; // 记录前驱顶点下标 int queue[MAX_VERTEX]; int front 0, rear 0; int found 0; // 初始化前驱数组为-1 for(int i 0; i G-numVertexes; i) predecessor[i] -1; visited[s] 1; queue[rear] s; while(front ! rear !found) { int v queue[front]; EdgeNode *p G-adjList[v].firstedge; while(p ! NULL) { int adj p-adjvex; if(!visited[adj]) { visited[adj] 1; predecessor[adj] v; // 记录是从v到达adj的 queue[rear] adj; if(adj t) { // 找到目标 found 1; break; } } p p-next; } } if(found) { // 回溯路径 int path[MAX_VERTEX], index 0; int cur t; while(cur ! -1) { path[index] cur; cur predecessor[cur]; } printf(从 %c 到 %c 的最短认识路径通过 %d 个人: , start, target, index-2); for(int i index-1; i 0; i--) { printf(%c, G-adjList[path[i]].data); if(i 0) printf( - ); } printf(\n); } else { printf(用户 %c 和 %c 之间没有连通路径。\n, start, target); } }测试这个功能int main() { GraphAdjList G; // 假设初始化图添加一些用户和好友关系 // CreateALGraph(G); // 或者手动添加 G.numVertexes 0; G.numEdges 0; AddVertex(G, A); // 用户A AddVertex(G, B); // 用户B AddVertex(G, C); AddVertex(G, D); AddVertex(G, E); AddEdge(G, A, B); // A和B是好友 AddEdge(G, A, C); // A和C是好友 AddEdge(G, B, D); // B和D是好友 AddEdge(G, C, D); // C和D是好友 AddEdge(G, D, E); // D和E是好友 // 查找A到E的最短路径 BFS_ShortestPath(G, A, E); // 输出A - C - D - E (通过2个人) BFS_ShortestPath(G, A, D); // 输出A - B - D 或 A - C - D (通过1个人) return 0; }这个简单的例子展示了如何将基础的图操作和遍历算法结合起来解决一个实际的问题。BFS在这里完美地扮演了“寻找最少中间人”的角色。5. 性能考量与工程实践中的陷阱在学校做算法题图的规模可能很小。但在实际工程中图可能拥有数百万甚至数十亿的顶点和边如社交网络、网页链接图。这时每一个基础操作的实现细节都至关重要。1. 空间效率是首要考虑对于超大规模稀疏图邻接矩阵完全不可行。邻接表是唯一选择但链表指针带来的内存开销也不容小觑。在C中vectorvectorint向量套向量通常比vectorlistint向量套链表有更好的缓存局部性访问更快。在追求极致性能时甚至会使用压缩稀疏行CSR等格式。2. 顶点ID的映射我们例子中用字符表示顶点实际中可能是字符串用户名、数字ID或复杂对象。直接将其作为数组下标不现实。通常的作法是维护一个从顶点数据到内部整数ID0,1,2,...的映射哈希表。图的内部操作全部使用整数ID高效且统一。只在输入输出时进行映射转换。 这解释了为什么我们的LocateVex函数如此重要它是连接外部数据和内部表示的桥梁。3. 边的去重与快速查找在添加边时我们遍历链表检查是否重复时间复杂度是O(度)。对于度数很高的顶点网络中的“大V”这可能很慢。工程上可能会使用哈希集合如C的unordered_set代替链表来存储邻接点将查找复杂度降至平均O(1)。或者在批量建图时先收集所有边排序去重后再构建邻接表。4. 遍历中的“已访问”标记我们的visited数组是全局的、与顶点数同大小的整型数组。在多次遍历或图非常大时反复初始化这个数组O(V)会成为瓶颈。一个优化技巧是使用“时间戳”或“代”的概念用一个全局计数器mark。每个顶点存储一个last_visited标记。每次遍历时mark。判断一个顶点是否被访问过只需看它的last_visited是否等于当前的mark。这样就避免了每次遍历前对整个数组的初始化。5. 内存管理在C语言中我们手动malloc和free边节点。在删除顶点或整个图时必须小心地释放所有链表内存防止内存泄漏。在更高级的语言中如Java, Python虽然垃圾回收器会帮忙但对于长期运行的服务仍要注意对象引用避免因缓存等原因导致图节点无法被回收。6. 并发访问如果图结构需要被多个线程同时读取和修改例如一个实时更新的推荐系统那么基本的邻接表操作就不是线程安全的。在顶点i的链表上插入一条边时另一个线程可能正在遍历这个链表导致不可预知的行为。这时需要引入锁机制如读写锁或者采用并发数据结构但这会显著增加复杂度并影响性能。6. 如何测试你的图实现写完代码只是第一步确保其正确性更为关键。对于图这种复杂的数据结构需要有系统的测试策略。1. 单元测试基础操作建图与查询创建一个小图测试LocateVex、顶点度数计算是否正确。增删边添加一条边验证两个顶点的邻接表中是否都出现对方。删除边后再次验证是否消失。特别注意删除最后一条边或重复删除的情况。增删顶点添加顶点验证顶点数组和计数。删除一个顶点尤其是中间顶点验证1其所有关联边是否被删除2末尾顶点是否被正确移动3其他顶点对它的引用是否被正确更新。这是最容易出错的环节。2. 遍历测试连通图创建一个简单的链状或星状图手动推导DFS和BFS顺序与程序输出对比。非连通图创建两个互不连接的子图测试遍历入口函数是否能访问到所有顶点。有向图调整你的代码支持有向边只在起点的邻接表中添加边测试遍历顺序是否符合预期。3. 算法功能测试最短路径使用我们上面实现的BFS_ShortestPath在不同形状的图上测试直线、分叉、环验证其输出的路径是否确实是最短的。边界条件测试起点等于终点、起点终点不连通、图中只有一个顶点、空图等情况程序是否能优雅处理不会崩溃或输出错误结果。4. 压力与性能测试可选生成大规模随机图例如1万个顶点10万条边测试建图、遍历、最短路径查询的时间是否符合预期例如BFS时间复杂度应为O(VE)。使用内存分析工具如Valgrind检查C/C实现中是否存在内存泄漏。一个实用的技巧是将你的图实现封装成独立的模块.c和.h文件并编写一个全面的测试程序覆盖上述所有情况。这不仅能保证代码质量未来扩展功能如加权图、最小生成树算法时也能快速验证基础是否稳固。图的基本操作是数据结构中承上启下的关键一环。它既需要你扎实掌握指针、链表、数组、队列、栈这些基础又是你学习最短路径、最小生成树、拓扑排序、网络流等高级算法的必经之路。我建议在理解的基础上自己动手将邻接矩阵和邻接表两种实现都敲一遍并完成增删查改和遍历操作。过程中遇到的每一个编译错误和逻辑Bug都会让你对图在内存中的形态有更深的理解。当你能够不假思索地写出非递归DFS和记录路径的BFS时这些知识才真正变成了你自己的东西。