图的两种核心存储结构：邻接矩阵与邻接表深度解析

简介本资源是一份面向计算机专业本科生及数据结构初学者的图存储结构实践教学材料聚焦邻接矩阵与邻接表两种核心表示方法的原理对比、相互转换及C语言实现。内容涵盖有向图的存储建模、双向转换算法MatToList/ListToMat、内存动态分配细节、输入交互扩展设计并附完整可运行代码与详细注释适用于课程实验、课程设计及算法基础巩固。资源为单文件Word文档.docx共1个文件大小55KB结构清晰含实验目的、问题描述、实现要求、完整源码及运行示例截图便于直接阅读与代码复现。已有8612人学习下载读者可即刻掌握图的两种存储结构本质差异、转换逻辑与工程实现要点为后续图算法如DFS/BFS、最短路径打下坚实基础。1. 图的两种“身份证”邻接矩阵和邻接表到底是什么想象你刚加入一个新公司HR给你发了两份员工通讯录——一份是Excel大表格600人×600人横纵都是姓名格子里写着“是直属下属”“是跨部门协作”“无工作交集”。查张三和李四有没有汇报关系秒翻第37行第124列一眼见分晓。但99%的格子都空着整张表打印出来能铺满会议室地板。另一份是手写小卡片册每人一张卡背面只贴着他实际对接的3–5个人的名字和关系比如“张三技术总监审批我的需求”。查张三的下属翻他那张卡3个名字跃然纸上但想确认李四是否向张三汇报得把全册600张卡挨个翻一遍直到找到李四那张、再看他写的“上级”栏。这两份通讯录就是图的邻接矩阵和邻接表——它们不是算法不是代码而是图在计算机里最基础的“存法”。你不会用邻接矩阵去跑最短路径也不会拿邻接表直接画拓扑图但所有图算法比如Dijkstra、DFS、连通性判断都必须先从这两种“身份证”里读出“谁和谁有边”就像HR系统必须先从通讯录里确认组织关系才能算审批流。很多人学图时一头扎进BFS遍历却卡在“为什么我的邻接表遍历总漏节点”根源往往不是逻辑错而是没真正看懂这张“身份证”怎么填、怎么查。搞懂它不是为了背定义而是让你以后看到任何图相关问题第一反应不再是“该用什么算法”而是“这个图该怎么存才不翻车”。2. 邻接矩阵用“方阵”存关系快查慢建还占地方2.1 它长什么样—— 一张“顶点对顶点”的打分表邻接矩阵本质是一个二维数组arcs[i][j]行和列都代表图的顶点比如顶点0、1、2…每个格子存的是“从顶点i到顶点j”这条边的信息。有向图arcs[2][5] 7表示“从顶点2指向顶点5有一条权重为7的边”而arcs[5][2]可能是0无反向边或别的值无向图矩阵一定对称arcs[2][5]和arcs[5][2]必须相等比如都是1表示两点间有边权值存储格子里不只能存0/1还能存距离、费用、延迟等数值如代码中p-info g-arcs[i][j]就是把矩阵里的权值复制到邻接表节点里。提示代码里#define INF 32767是个经典技巧——用一个极大数而非-1表示“无穷大/不存在边”避免负权图计算时出错。打印时遇到INF就显示---视觉上立刻区分“真无边”和“权值为0”。2.2 它为什么快—— 一次下标计算直达答案查任意两个顶点是否有边只需if (arcs[i][j] ! 0)——时间复杂度 O(1)。为什么这么快因为内存里二维数组是连续存储的arcs[i][j]的地址 起始地址 i × 列数 × 单元大小 j × 单元大小。CPU不用遍历直接算出位置像查字典翻页一样精准。这也是它适合频繁查询边存在性场景的原因比如社交平台实时检测“用户A是否关注用户B”数据库索引背后常隐含邻接矩阵思想。2.3 它的代价是什么—— 空间爆炸与稀疏图灾难假设一个城市交通网有10万个路口顶点但平均每个路口只连3条路边。邻接矩阵需要10^5 × 10^5 10^10个整数空间约40GB内存——而实际存在的边只有10^5 × 3 ≈ 3×10^5条存储利用率不到0.0003%。代码中#define MAX_VERTEX_NUM 20看似安全但若真实项目顶点数达上千AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]会瞬间吃光栈空间C语言中大数组放栈易爆栈。生产环境必须改用动态分配// 正确做法堆上分配按需申请 int **createAdjMatrix(int n) { int **mat (int **)malloc(n * sizeof(int *)); for (int i 0; i n; i) { mat[i] (int *)malloc(n * sizeof(int)); for (int j 0; j n; j) mat[i][j] 0; // 初始化 } return mat; }注意原代码AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]是栈分配顶点数超20必崩溃而实验用6个顶点只是教学简化切勿照搬上线。2.4 它怎么建—— 手动填表还是程序生成实验中用了静态数组初始化int A[][6] { {0,5,0,7,0,0}, // 顶点0到1有边(权5)到3有边(权7) {0,0,4,0,0,0}, // 顶点1到2有边(权4) {8,0,0,0,0,9}, // 顶点2到0有边(权8)到5有边(权9) // ... 其余行 };这种写法直观但无法处理用户输入的动态图。真实场景需改造为先读入顶点数n和边数e用memset(arcs, 0, sizeof(arcs))清零整个矩阵循环e次每次读入u, v, weight执行arcs[u][v] weight。—— 这才是工业级写法也是实验要求“手动输入任意图形”的底层逻辑。3. 邻接表用“链表集合”存关系省空间但查边要遍历3.1 它长什么样—— 每个顶点配一个“联系人列表”邻接表由两部分组成顶点表vertices[]数组每个元素是结构体VNode存顶点数据如名称、ID和指向第一条边的指针firstarc边链表每个VNode的firstarc指向一个ArcNode链表链表节点存“邻接顶点编号adjvex”、“边权值info”和“下一个节点指针nextarc”。打个比方顶点表是微信通讯录里的好友列表而每个好友点开后的“聊天记录”就是它的邻接表链表——只存真实发生过的对话边没有“可能聊但没聊过”的占位符。3.2 它为什么省空间—— 只为存在的边分配内存存储空间 顶点数 × 顶点结构体大小 边数 × 边节点大小。对于前述10万路口的稀疏图邻接表仅需约10^5 × (sizeof(VNode) 3×sizeof(ArcNode)) ≈ 几MB比邻接矩阵的40GB小4个数量级。代码中ArcNode *p (ArcNode *)malloc(sizeof(ArcNode))正是为每条边单独申请内存动态伸缩——这才是它应对海量稀疏数据的核心能力。3.3 它的查询代价是什么—— 查单个邻居快查全局关系慢查顶点v的所有邻居从vertices[v].firstarc开始遍历链表时间复杂度O(degree(v))degree(v)是v的出度查“v到u是否有边”必须遍历v的整个链表最坏O(degree(v))查“是否存在任意一条边”得遍历所有顶点的链表O(总边数)。所以邻接表绝非“万能省空间方案”。比如做“图是否连通”判断时若频繁检查任意两点连通性邻接表反而比邻接矩阵慢——此时应预处理成并查集或Floyd-Warshall而非硬扛链表遍历。3.4 它怎么建—— 头插法 vs 尾插法顺序影响可读性实验代码用的是头插法p-nextarc G-vertices[i].firstarc; G-vertices[i].firstarc p;新边永远插在链表最前面。好处代码简洁插入 O(1)坏处最终链表顺序与输入边顺序相反。比如按0→1, 0→3, 0→5输入打印时却显示5,3,1。若需保持输入顺序如调试时对照原始数据应改用尾插法// 尾插法伪代码需维护 tail 指针 ArcNode *tail G-vertices[i].firstarc; if (tail NULL) { // 链表空首节点即尾节点 G-vertices[i].firstarc p; } else { while (tail-nextarc ! NULL) tail tail-nextarc; tail-nextarc p; } p-nextarc NULL;注意原代码for(jn-1;j0;j--)的逆序循环正是为配合头插法让输出“看起来”更接近输入顺序属于教学取巧实际项目中应明确选择插入策略并注释清楚。4. 邻接矩阵 ↔ 邻接表转换不是魔法是遍历重建4.1 矩阵转邻接表扫描每一行为非零格子建节点核心逻辑在MatToList()函数for(i0; in; i) { // 遍历每个顶点i矩阵的每一行 for(j0; jn; j) { // 遍历该顶点的所有可能邻居j矩阵的每一列 if(g-arcs[i][j] ! 0) { // 若i到j有边 p (ArcNode*)malloc(sizeof(ArcNode)); // 为这条边分配节点 p-adjvex j; // 记录邻居j p-info g-arcs[i][j]; // 记录权值 p-nextarc G-vertices[i].firstarc; // 头插法接在现有链表前 G-vertices[i].firstarc p; // 更新顶点i的链表头 } } }关键点外层i循环对应“谁发出边”内层j循环对应“边指向谁”if(g-arcs[i][j] ! 0)是判断条件!0而非0因为权值可能为负如某些图算法中G-vertices[i].firstarc NULL初始化必须做否则未赋值的指针是随机值遍历时直接段错误。4.2 邻接表转矩阵清空矩阵再逐条边填值ListToMat()的逻辑更直白// 第一步清空矩阵重要否则残留旧数据 for(i0; in; i) for(j0; jn; j) g-arcs[i][j] 0; // 第二步遍历每个顶点i的链表 for(i0; in; i) { p G-vertices[i].firstarc; // 获取顶点i的第一条边 while(p ! NULL) { // 遍历i的所有出边 g-arcs[i][p-adjvex] p-info; // 填矩阵i行p-adjvex列 权值 p p-nextarc; // 移动到下一条边 } }血泪经验清空矩阵这一步极易被忽略若矩阵之前存过其他图的数据不初始化会导致“幽灵边”——明明邻接表里没有某条边矩阵里却残留着旧值后续算法全乱套。这是初学者调试时最常踩的坑。4.3 转换中的权值陷阱INF、0、负数如何处理原代码用INF32767表示“无边”但转换时if(g-arcs[i][j]!0)会把INF当作有效边因INF!0。正确做法应统一约定无边标记用0无权图或INF带权图但判断条件必须匹配权值为0的边在无权图中0表示无边故不能存在权值为0的边在带权图中需额外约定0是否合法如交通网中“距离0”可能表示同一地点。实验代码默认0表示无边因此A[][6]中的0都是占位符非实际权值——这限制了它处理真正含0权值图的能力。4.4 转换的边界自环、重边、孤立点怎么存自环顶点到自己邻接矩阵中arcs[i][i]可存非零值邻接表中ArcNode-adjvex i即可无需特殊处理重边i到j多条边邻接矩阵只能存一条取最后赋值天然不支持邻接表可存多个ArcNodeadjvex相同但info不同孤立点无边顶点邻接矩阵中该行/列全0邻接表中vertices[i].firstarc NULL链表为空。提示实验代码未处理重边若需支持应在邻接表插入时改为追加节点而非覆盖或改用多重邻接表每个节点存边数计数。5. 邻接矩阵和邻接表到底谁是谁五个常见误区一锅端5.1 误区一“邻接表就是链表邻接矩阵就是二维数组” → 混淆数据结构与存储逻辑为什么混教材常强调“邻接表用链表实现”导致学生以为只要用了链表就是邻接表又见矩阵是二维数组就认为所有二维数组存图都是邻接矩阵。怎么区分邻接表的本质是“顶点导向的边集合”每个顶点独立管理自己的邻接边边之间无全局顺序邻接矩阵的本质是“顶点对关系的全量映射”强制建立所有顶点对的坐标系无论边是否存在✅ 正确实践用哈希表替代链表实现邻接表如unordered_mapint, vectorpairint,int仍是邻接表用一维数组模拟二维arcs[i*nj]存邻接矩阵仍是邻接矩阵。❌ 反例用链表存所有边不分顶点是“边列表”不是邻接表用二维数组存顶点坐标x,y不是邻接矩阵。5.2 误区二“稀疏图必须用邻接表稠密图必须用邻接矩阵” → 忽略访问模式才是关键为什么混教科书说“邻接表省空间”于是看到“稀疏”就条件反射选邻接表完全不管实际操作。怎么区分场景推荐存储原因说明社交网络查“好友的好友”邻接表需遍历某顶点所有邻居O(degree)邻接表天然支持导航软件查“A到B是否直达”邻接矩阵频繁随机查询边存在性O(1)邻接矩阵碾压邻接表的O(degree)游戏地图寻路A*算法邻接表A*需反复获取顶点邻居并排序邻接表遍历邻居更快且游戏地图通常稀疏路少编译器依赖分析大量头文件包含邻接矩阵需快速计算传递闭包Floyd算法其时间复杂度O(n³)在邻接矩阵上最简洁邻接表需先转矩阵关键结论决定因素不是图本身稀疏/稠密而是你的算法最常执行什么操作。就像买刀不看菜板大小而看你要切丝还是剁骨。5.3 误区三“邻接表转换后打印顺序乱代码写错了” → 不懂头插法的必然结果为什么混看到DispAdj()输出5,3,1而输入是1,3,5就断定MatToList()有bug。怎么区分头插法实验所用新节点永远插链表头所以最后输入的边出现在最前面尾插法新节点插链表尾输出顺序与输入一致✅ 验证方法在MatToList()插入前加printf(Inserting edge %d-%d\n, i, j);观察打印顺序与输出链表是否一致❌ 错误归因不查插入逻辑直接重写整个转换函数反而引入新bug。5.4 误区四“邻接矩阵不能存有向图” → 对矩阵对称性理解片面为什么混无向图邻接矩阵对称学生误以为“不对称就不是邻接矩阵”。怎么区分有向图邻接矩阵天然不对称arcs[i][j]1表示 i→j 有边arcs[j][i]可为0无j→i边对称性只是无向图的特例不是邻接矩阵的定义要求✅ 实验证据代码中A[][6]的第2行{8,0,0,0,0,9}顶点2→0和2→5有边而第0行{0,5,0,7,0,0}中arcs[0][2]0明显不对称❌ 反例强行让有向图矩阵对称如arcs[i][j] arcs[j][i] 1就变成了无向图语义错误。5.5 误区五“转换程序能跑通就代表理解了” → 忽略内存泄漏和边界安全为什么混main()里调用MatToList()后没释放G的内存程序退出自动回收误以为“没问题”。怎么区分内存泄漏G(ALGraph *)malloc(sizeof(ALGraph))分配了内存但全程未free(G)若在循环中反复调用内存持续增长野指针风险MatToList()中p (ArcNode*)malloc(...)后若malloc失败返回NULL代码未检查就直接p-adjvexj必然崩溃✅ 生产级写法p (ArcNode*)malloc(sizeof(ArcNode)); if (p NULL) { fprintf(stderr, Memory allocation failed!\n); exit(1); } // ... 使用p // 最后在程序结束前 free所有malloc的内存6. 什么时候该用邻接矩阵什么时候死磕邻接表一个真实踩坑案例去年某高校课程设计学生A要做“校园快递柜网络优化”需求给定N个快递柜顶点M条双向运输路线边有权重运输时间求任意两柜间的最短运输时间学生A的做法用邻接表存图因听说“图都用邻接表”对每对顶点(i,j)跑一次DijkstraO(M log N)总时间复杂度 O(N²M log N)N500时预估运行15分钟结果程序跑了2小时没出结果服务器内存爆满被老师叫停。复盘发现三个致命错误存储选型错误需求是“求所有顶点对最短路径”最优解是Floyd-Warshall算法其时间复杂度 O(N³)但必须基于邻接矩阵——因为算法核心是三重循环for(k) for(i) for(j) arcs[i][j] min(arcs[i][j], arcs[i][k]arcs[k][j])需要随机访问arcs[i][k]和arcs[k][j]邻接表无法高效支持空间预估失误N500时邻接矩阵需500²×4B 1MB而邻接表在稠密图中M≈N²实际占用更大链表指针开销未做输入校验用户输入边时若重复输入0→1两次邻接表会存两条边Floyd算法仍能处理但邻接矩阵会覆盖需提前去重——这恰是邻接矩阵的“优势场景”天然去重。正确解法// 1. 用邻接矩阵存图支持Floyd int **dist createAdjMatrix(n); // 初始化为INF for each edge (u,v,w) { dist[u][v] w; dist[v][u] w; // 无向图双向赋值 } // 2. Floyd-Warshall30行核心代码 for (int k 0; k n; k) { for (int i 0; i n; i) { for (int j 0; j n; j) { if (dist[i][k] ! INF dist[k][j] ! INF) { dist[i][j] min(dist[i][j], dist[i][k] dist[k][j]); } } } } // 3. 查询O(1)printf(Time from %d to %d: %d\n, u, v, dist[u][v]);N500时Floyd仅需500³ 1.25亿次操作现代CPU 1秒内完成。从那以后我每次接到图需求都强制走一遍“三问流程”问操作我要做的最多操作是什么查边遍历邻居求最短路径问规模顶点数N和边数M的大致范围N100M≈N²MN²问扩展未来可能加什么功能比如现在只查单源但下周要查所有对—— 如果第一问是“高频随机查边”第二问是“N1000”第三问是“可能加全局分析”我立刻选邻接矩阵如果第一问是“遍历所有邻居做聚合”第二问是“N10⁶, M10⁷”第三问是“只做单次分析”我闭眼选邻接表。希望帮到你。本文还有配套的精品资源点击获取