互联网数据结构—图思维导图
简单介绍数据结构—图的内容
树图思维导图提供 互联网数据结构—图思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 互联网数据结构—图思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：0215ec7c39ec7ba8fa3f88d0b111ef79
思维导图大纲
数据结构——图思维导图模板大纲
图的定义和基本术语
定义
是由一个顶点集V和一个顶点间的关系集合组成的数据结构
分类
有向图
无向图
基本术语
子图
完全图
含有e=n(n-1)/2条边的无向图
有向完全图
含有e=n(n-1）条弧的有向图
稀疏图
边或弧的个数＜nlogn
稠密图
边或弧的个数＞＝nlogn
度（入度＋出度）
出度
以顶点v为弧头的弧的数目
入度
以顶点v为弧尾的弧的数目
路径长度
路径上边的数目
连通图
图中任意两个顶点之间都有路径相通
有（无）向网
弧或边带权的图
图的遍历
深度优先搜索DPS
类似于先序遍历
实质
对每个顶点查找其邻接点的过程
广度优先搜索BFS
实质
通过边或弧找邻接点的过程
图的存储结构
邻接矩阵
无向图：不对称
统计第j列1的个数可得顶点j的入度
有向图：对称
统计第i行1的个数可得顶点i的出度
邻接表
只存储图中已有的弧或边的信息
有向图的十字链表
将有向图的邻接表和逆邻接表结合起来的一种链
图的应用
最小生成树
普里姆（Prim）算法
贪心算法
最短路径
Dijkstra算法
Floyd算法
拓扑排序
关键路径
相关思维导图模板
树图思维导图提供 RBT工作管理计划 在线思维导图免费制作，点击“编辑”按钮，可对 RBT工作管理计划 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：07511cf9c98d75f4a7a974d65f912b8f
树图思维导图提供 科技计划项目资金预算编制总体要求的学习和整理 在线思维导图免费制作，点击“编辑”按钮，可对 科技计划项目资金预算编制总体要求的学习和整理 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：49470946de6296e1813ed1ed5efc14ba
沪公网安备 31011502019485号
上海工商