计算机知识拓扑排序思维导图
简单介绍拓扑排序的内容
树图思维导图提供 计算机知识拓扑排序思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 计算机知识拓扑排序思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：77c3ddf8ad020c8d89d86c687b17ce18
思维导图大纲
拓扑排序思维导图模板大纲
相关概念
有向无环图DAG
若一个有向图中不存在环，则称为有向无环图，简称DAG图
AOV网
若用DAG图表示一个工程，其顶点表示活动，用有向边<Vi,Vj>表示活动Vi先于Vj的关系，则将这种图称为顶点表示活动的网络，简称AOV网
定义
若一个有向无环图的顶点组成的序列，满足
①每个顶点只出现一次
②若A顶点在B前面，则图中不存在从B顶点到A顶点的路径
拓扑排序是对有向无环图的顶点的一种排序，每个DAG图有一个或多个拓扑排序
算法
①选择一个没有前驱的顶点并输出
②删除该顶点并所有以它为起点的边
③重复①②，直到DAG图为空，若不为空，则有向图必存在环
用深度优先遍历也可实现拓扑排序
时间复杂度
由于删除了顶点又要删除边，故时间复杂度为O(V+E)
特点
若一个顶点有多个后继，则拓扑排序的结果通常不唯一
若各个顶点已经排在一个线性有序的序列中，每个顶点有唯一的前驱后继的关系，再做拓扑排序时，排序结果是唯一的
拓扑排序生成的DAG图用邻接矩阵存储表示，这种邻接矩阵可以是三角矩阵
对于一般的图来说，若其邻接矩阵是三角矩阵，则存在拓扑排序，反之不一定成立
概括思维导图模板大纲
相关思维导图模板
树图思维导图提供 计算机辅助电子线路设计 在线思维导图免费制作，点击“编辑”按钮，可对 计算机辅助电子线路设计 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：6ca7534122e478b7cd1b28b3c72601e8
树图思维导图提供 计算机网络应用层 在线思维导图免费制作，点击“编辑”按钮，可对 计算机网络应用层 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：1d7a27cc460774320c29f068a3a669b8
沪公网安备 31011502019485号
上海工商