图的存储思维脑图思维导图
四大图的存储方式及总结内容分解
树图思维导图提供 图的存储思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 图的存储思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：8122e9719fd887257f091e521f40ab43
思维导图大纲
图的存储思维导图模板大纲
邻接矩阵法
一图胜千言
带权图
求顶点的度
无向图的第i个结点的度 = 第i行（或列）中非0（非∞）的个数
有向图第i个节点出度 = 第i行非0个数
有向图第i个节点入度 = 第i列非0个数
有向图第i个节点度 = 第i行、第i列非0个数之和
用邻接矩阵求度时间复杂度为O（|V|）
特点
空间复杂度O(|V|^2)，只和顶点数有关，与边无关
适合存稠密图
无向图邻接矩阵是对称矩阵，可以压缩存储
邻接矩阵性质
十字链表法
一图胜千言
空间复杂度O(|V|+|E|)
只能存有向图
邻接多重表法
一图胜千言
总结
最重要的一集
对邻接表来说，ArcNode为边表结点
无向图的边表节点数 = 边数 * 2
对邻接矩阵来说
有向图边数 = 矩阵中非0个数
无向图边数 = 矩阵中非0个数 / 2
邻接表法
一图胜千言
求顶点的度、出入边
沿着一行遍历就是出度
求某结点入度要遍历整个图
因此对有向图来说求入度、度、入边很不方便
无向图边结点数量为2|E|，有向图边结点数量为|E|
特点
同一个图，邻接表表示方式不唯一
同一个图，邻接矩阵表示唯一
存储稀疏图
空间复杂度
无向图O(|V|+2|E|)
有向图O(|V|+|E|)
相关思维导图模板
树图思维导图提供 一、研究内容 在线思维导图免费制作，点击“编辑”按钮，可对 一、研究内容 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：4f21797dd3e8b08f1951dfc24e7be94f
树图思维导图提供 904名中国成年人第三磨牙相关知识、态度、行为和病史的横断面调查 在线思维导图免费制作，点击“编辑”按钮，可对 904名中国成年人第三磨牙相关知识、态度、行为和病史的横断面调查 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：10b9a8a2dd2fb4593f8130ef16c320fc
沪公网安备 31011502019485号
上海工商