数据结构图的存储方式：从邻接矩阵到十字链表，一文打尽

数据结构图的存储方式从邻接矩阵到十字链表一文打尽图是计算机科学中最灵活、最强大的数据结构之一。社交网络、地图导航、推荐系统……背后都离不开图。但图的存储方式直接影响算法的效率。今天我们就来彻底搞清楚图的五种存储方式。作为一名从 Java 后端转算法的开发者我深知图存储的重要性。选错了存储方式一个简单的遍历都可能从 O(n) 变成 O(n²)甚至内存爆炸。本文将从最基础的邻接矩阵讲起逐步深入到十字链表、邻接多重表等高级结构帮你建立完整的知识体系。一、图的存储到底在存什么图由顶点和边组成。存储图的核心就是存储顶点信息比如编号、数据存储边的关系谁和谁相连权重多少根据图的类型有向/无向、带权/无权、稀疏/稠密我们选择不同的存储方式。二、五种主流存储方式对比速览存储方式适用图类型空间复杂度判断边是否存在遍历邻接点备注邻接矩阵稠密图O(V²)O(1)O(V)简单直观但浪费空间邻接表稀疏图O(VE)O(degree)O(degree)最常用但删除边较慢逆邻接表有向图入边查询O(VE)O(degree)O(degree)邻接表的伴生结构十字链表有向图O(VE)O(1) 可优化O(degree)可同时遍历出边和入边邻接多重表无向图边操作频繁O(VE)O(1) 可优化O(degree)避免边的重复存储下面逐一详细讲解。三、邻接矩阵Adjacency Matrix—— 简单粗暴3.1 定义用一个 V × V 的二维矩阵M表示图。对于无权图M[i][j] 1表示顶点 i 到 j 有边M[i][j] 0表示无边对于带权图将 1 替换为权重0 替换为无穷大∞。3.2 示例无向图顶点: 0, 1, 2, 3 边: 0-1, 0-2, 1-3, 2-3 邻接矩阵 0 1 2 3 0 [ 0, 1, 1, 0 ] 1 [ 1, 0, 0, 1 ] 2 [ 1, 0, 0, 1 ] 3 [ 0, 1, 1, 0 ]3.3 优缺点优点判断两点是否有边O(1)实现简单适合稠密图缺点空间 O(V²)V10000 时矩阵有 1 亿个元素内存爆炸遍历某个顶点的所有邻接点需要 O(V)即使该顶点只有少数几个邻居3.4 Java 代码publicclassAdjacencyMatrix{privateint[][]matrix;privateintvertexCount;publicAdjacencyMatrix(intvertexCount){this.vertexCountvertexCount;matrixnewint[vertexCount][vertexCount];}// 添加边无向图publicvoidaddEdge(inti,intj){matrix[i][j]1;matrix[j][i]1;}// 判断边是否存在publicbooleanhasEdge(inti,intj){returnmatrix[i][j]1;}// 遍历顶点 v 的所有邻接点publicListIntegergetNeighbors(intv){ListIntegerneighborsnewArrayList();for(inti0;ivertexCount;i){if(matrix[v][i]1){neighbors.add(i);}}returnneighbors;}}四、邻接表Adjacency List—— 稀疏图王者4.1 定义为每个顶点维护一个链表或动态数组存储所有邻接点。对于带权图链表节点还需存储权重。4.2 示例无向图同上0 - 1 - 2 1 - 0 - 3 2 - 0 - 3 3 - 1 - 2有向图0 - 1 - 2 1 - 3 2 - 3 3 - (空)4.3 优缺点优点空间 O(VE)非常适合稀疏图|E| |V|²遍历邻接点的时间 O(degree(v))高效缺点判断边是否存在需要遍历邻接链表最坏 O(degree)删除边稍微麻烦4.4 Java 代码使用 ArrayListimportjava.util.*;publicclassAdjacencyList{privateListListIntegeradj;privateintvertexCount;publicAdjacencyList(intvertexCount){this.vertexCountvertexCount;adjnewArrayList(vertexCount);for(inti0;ivertexCount;i){adj.add(newLinkedList());}}publicvoidaddEdge(inti,intj){adj.get(i).add(j);adj.get(j).add(i);// 无向图}publicListIntegergetNeighbors(intv){returnadj.get(v);}publicbooleanhasEdge(inti,intj){returnadj.get(i).contains(j);}}五、逆邻接表Reverse Adjacency List—— 有向图的“反向索引”邻接表只能快速获取出边。如果经常需要查询哪些顶点指向我如 PageRank 算法就需要逆邻接表。实现额外维护一个reverseAdj数组每条有向边i→j同时添加到reverseAdj.get(j)中。空间仍然是 O(VE)但两倍常数。适用有向图中需要同时正向和反向遍历的场景。六、十字链表Orthogonal List—— 有向图的完美存储邻接表 逆邻接表需要两份边存储每条边被存两次。十字链表将出入边整合到一个节点中每条边只存储一次却能同时快速遍历出边和入边。6.1 节点结构顶点表data firstOut firstIn边表弧节点tailVex headVex tailLink headLink weight可选tailVex弧尾顶点下标headVex弧头顶点下标tailLink指向下一条以相同弧尾为起点的边headLink指向下一条以相同弧头为终点的边6.2 示例图解有向图0→1, 0→2, 1→3, 2→3顶点 0 的firstOut指向弧0→10→1的tailLink指向0→2。顶点 3 的firstIn指向弧1→31→3的headLink指向2→3。6.3 优点空间 O(VE)每条边只存储一次可同时高效遍历出边和入边删除边时无需在两个表中找6.4 适用场景有向图且需要频繁查询入边和出边如编译器中的依赖图、网络流算法。七、邻接多重表Adjacency Multi-list—— 无向图的边复用在无向图的邻接表中每条边会被存储两次在两个顶点的链表里。这导致删除或修改边时需要同时操作两个链表容易出错。邻接多重表让每条边只用一个节点两个顶点共享。7.1 节点结构顶点表data firstEdge边表mark vertex1 vertex2 path1 path2vertex1,vertex2边的两个顶点path1指向与vertex1相连的下一条边path2指向与vertex2相连的下一条边mark标记边是否被访问用于遍历7.2 优点每条边只存储一次节省空间删除边时只需删除一个节点操作简单适合对边频繁增删的场景7.3 适用场景无向图且边操作频繁例如最小生成树算法中动态维护边集合。八、如何选择一张决策图图是否稠密 │ ├── 是|E| ≈ |V|²→ 邻接矩阵 │ └── 否稀疏图 │ └── 是否无向图 │ ├── 是 ──→ 是否需要频繁删除边或遍历边 │ ├── 是 → 邻接多重表 │ └── 否 → 邻接表 │ └── 否有向图 │ └── 是否需要同时频繁遍历入边和出边 ├── 是 → 十字链表 └── 否 → 邻接表 可选逆邻接表九、实战建议场景推荐存储理由社交网络好友关系稀疏无向邻接表空间省遍历快地图导航有向带权稀疏邻接表或十字链表权重存储方便蛋白质相互作用网络稠密无向邻接矩阵判断连接 O(1)编译器依赖图有向十字链表同时查依赖和被依赖图算法教学演示邻接表实现简单十、总结图的存储没有银弹。理解每种方式的空间复杂度、操作效率和适用图类型才能在实际开发中做出正确选择。一句话记忆稠密用矩阵稀疏用邻接有向要双向十字链表强无向边多重删边不慌张。彩蛋Facebook 的社交图如何存储早期用邻接表因为稀疏后来发展到自研的 TAO 系统但底层思想依然离不开这些经典结构。如果你觉得有帮助欢迎点赞、收藏、转发本文首发于 CSDN未经授权禁止转载。