TreeMind树图在线AI思维导图
当前位置:树图思维导图模板资格考试计算机计算机拓扑排序思维导图

计算机拓扑排序思维导图

  收藏
  分享
免费下载
免费使用文件
树图周树人 浏览量:62022-11-12 16:07:14
已被使用1次
查看详情计算机拓扑排序思维导图

简单介绍拓扑排序的内容

树图思维导图提供 计算机拓扑排序思维导图 在线思维导图免费制作,点击“编辑”按钮,可对 计算机拓扑排序思维导图  进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:d83337101ed77c17d77c5bd1d915a6bd

思维导图大纲

拓扑排序思维导图模板大纲

相关概念

有向无环图DAG

若一个有向图中不存在环,则称为有向无环图,简称DAG图

AOV网

若用DAG图表示一个工程,其顶点表示活动,用有向边<Vi,Vj>表示活动Vi先于Vj的关系,则将这种图称为顶点表示活动的网络,简称AOV网

定义

若一个有向无环图的顶点组成的序列,满足

①每个顶点只出现一次

②若A顶点在B前面,则图中不存在从B顶点到A顶点的路径

拓扑排序是对有向无环图的顶点的一种排序,每个DAG图有一个或多个拓扑排序

算法

①选择一个没有前驱的顶点并输出

②删除该顶点并所有以它为起点的边

③重复①②,直到DAG图为空,若不为空,则有向图必存在环

用深度优先遍历也可实现拓扑排序

时间复杂度

由于删除了顶点又要删除边,故时间复杂度为O(V+E)

特点

若一个顶点有多个后继,则拓扑排序的结果通常不唯一

若各个顶点已经排在一个线性有序的序列中,每个顶点有唯一的前驱后继的关系,再做拓扑排序时,排序结果是唯一的

拓扑排序生成的DAG图用邻接矩阵存储表示,这种邻接矩阵可以是三角矩阵

对于一般的图来说,若其邻接矩阵是三角矩阵,则存在拓扑排序,反之不一定成立

概括思维导图模板大纲

相关思维导图模板

计算机系统结构思维导图思维导图

树图思维导图提供 计算机系统结构思维导图 在线思维导图免费制作,点击“编辑”按钮,可对 计算机系统结构思维导图  进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:d55735120bfc45f09e7d4f00035ca040

计算机网络病毒思维导图思维导图

树图思维导图提供 计算机网络病毒思维导图 在线思维导图免费制作,点击“编辑”按钮,可对 计算机网络病毒思维导图  进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:6f1c8acd6ded214123c400f4dfca2fee