C语言数据结构系列图基础篇C语言数据结构系列十三图的基础——存储与表示一、前言二、图的基本概念2.1 什么是图2.2 图的术语2.3 图的类型三、邻接矩阵3.1 什么是邻接矩阵3.2 图解3.3 创建图3.4 优缺点四、邻接表4.1 什么是邻接表4.2 图解4.3 创建图4.4 优缺点五、两种存储方式对比六、完整示例七、应用八、下篇预告C语言数据结构系列十三图的基础——存储与表示本篇目标理解图的概念掌握邻接矩阵和邻接表两种存储方式摘要本文是 C 语言数据结构系列第十三篇系统讲解图Graph的基础概念与两种核心存储方式。首先介绍图的定义、术语顶点、边、有向/无向、带权等与类型随后重点剖析邻接矩阵二维数组查询快 O(1)适合稠密图和邻接表链表存储节省空间 O(VE)适合稀疏图的原理、图解、创建代码及优缺点最后通过对比表格总结两者适用场景并给出完整可运行的 C 语言示例。适合正在学习数据结构、想掌握图存储实现的读者。一、前言哈喽小伙伴们今天我们进入图Graph的世界图是最复杂的数据结构可以表示各种关系️ 地图导航 社交网络 互联网 依赖关系北京上海广州深圳让我们开始今天的学习吧 二、图的基本概念2.1 什么是图图Graph由顶点Vertex和边Edge组成表示多对多的关系。2.2 图的术语术语说明示例顶点节点城市边连接关系道路有向图边有方向微博关注无向图边无方向微信好友带权图边有权值距离/费用完全图任意两点都有边-连通图任意两点可达-2.3 图的类型有向图ABC无向图ABC三、邻接矩阵3.1 什么是邻接矩阵 用二维数组表示图matrix[i][j]1表示i和j有边#defineMAX_VERTEX100typedefstruct{charvexs[MAX_VERTEX];// 顶点表intarc[MAX_VERTEX][MAX_VERTEX];// 邻接矩阵intvexNum,arcNum;}MGraph;3.2 图解ABC邻接矩阵A B C A [0, 1, 1] B [1, 0, 1] C [1, 1, 0]3.3 创建图voidcreateGraph(MGraph*G,charvexs[],intn,intedges[][2],intm){G-vexNumn;G-arcNumm;// 初始化顶点for(inti0;in;i){G-vexs[i]vexs[i];}// 初始化矩阵for(inti0;in;i){for(intj0;jn;j){G-arc[i][j]0;}}// 填充边for(inti0;im;i){intv1edges[i][0];intv2edges[i][1];G-arc[v1][v2]1;G-arc[v2][v1]1;// 无向图}}3.4 优缺点优点缺点实现简单空间O(V²)查询快O(1)稀疏图浪费空间适合稠密图-四、邻接表4.1 什么是邻接表 用链表存储每个顶点的邻接点节省稀疏图的空间typedefstructArcNode{intadjvex;structArcNode*next;}ArcNode;typedefstruct{chardata;ArcNode*first;}VNode;typedefstruct{VNode vertices[MAX_VERTEX];intvexNum,arcNum;}ALGraph;4.2 图解图 A -- B A -- C B -- C 邻接表 A - B - C - NULL B - A - C - NULL C - A - B - NULL4.3 创建图voidcreateGraph(ALGraph*G,charvexs[],intn,intedges[][2],intm){G-vexNumn;G-arcNumm;for(inti0;in;i){G-vertices[i].datavexs[i];G-vertices[i].firstNULL;}for(inti0;im;i){intv1edges[i][0];intv2edges[i][1];ArcNode*node(ArcNode*)malloc(sizeof(ArcNode));node-adjvexv2;node-nextG-vertices[v1].first;G-vertices[v1].firstnode;node(ArcNode*)malloc(sizeof(ArcNode));node-adjvexv1;node-nextG-vertices[v2].first;G-vertices[v2].firstnode;}}4.4 优缺点优点缺点空间O(VE)查询慢O(度)适合稀疏图实现稍复杂节省空间-五、两种存储方式对比特性邻接矩阵邻接表空间O(V²)O(VE)查询边O(1)O(度)遍历邻接点O(V)O(度)适用场景稠密图稀疏图六、完整示例#includestdio.h#includestdlib.h#includestdbool.h#defineMAX_VERTEX100// 邻接矩阵typedefstruct{charvexs[MAX_VERTEX];intarc[MAX_VERTEX][MAX_VERTEX];intvexNum,arcNum;}MGraph;// 邻接表typedefstructArcNode{intadjvex;structArcNode*next;}ArcNode;typedefstruct{chardata;ArcNode*first;}VNode;typedefstruct{VNode vertices[MAX_VERTEX];intvexNum,arcNum;}ALGraph;// 查找顶点下标intlocateVex(MGraph*G,charv){for(inti0;iG-vexNum;i){if(G-vexs[i]v)returni;}return-1;}// 创建无向图邻接矩阵voidcreateMGraph(MGraph*G){printf(输入顶点数和边数: );scanf(%d %d,G-vexNum,G-arcNum);printf(输入顶点: );for(inti0;iG-vexNum;i){scanf( %c,G-vexs[i]);}for(inti0;iG-vexNum;i){for(intj0;jG-vexNum;j){G-arc[i][j]0;}}printf(输入边如 AB:\n);for(inti0;iG-arcNum;i){charv1,v2;scanf( %c%c,v1,v2);inti1locateVex(G,v1);inti2locateVex(G,v2);G-arc[i1][i2]1;G-arc[i2][i1]1;}}// 打印邻接矩阵voidprintMGraph(MGraph*G){printf(\n邻接矩阵:\n );for(inti0;iG-vexNum;i){printf(%c ,G-vexs[i]);}printf(\n);for(inti0;iG-vexNum;i){printf(%c ,G-vexs[i]);for(intj0;jG-vexNum;j){printf(%d ,G-arc[i][j]);}printf(\n);}}// 打印邻接表voidprintALGraph(ALGraph*G){printf(\n邻接表:\n);for(inti0;iG-vexNum;i){printf(%c - ,G-vertices[i].data);ArcNode*pG-vertices[i].first;while(p){printf(%d ,p-adjvex);pp-next;}printf(\n);}}intmain(){MGraph G;createMGraph(G);printMGraph(G);return0;}七、应用社交网络好友关系地图导航️路线规划编译器依赖⚙️拓扑排序网络路由最短路径八、下篇预告下一篇我们将学习图的遍历DFS与BFSDFS: 深度优先BFS: 广度优先学习建议图的存储方式要根据稀疏/稠密选择觉得有帮助就点赞收藏关注吧