有向无环图与拓扑排序思维导图
拓扑排序等相关内容分解
树图思维导图提供 有向无环图与拓扑排序 在线思维导图免费制作，点击“编辑”按钮，可对 有向无环图与拓扑排序 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：f40466dab35d1c2ea8856b751cb1b068
思维导图大纲
有向无环图与拓扑排序思维导图模板大纲
有向无环图DAG
一个有向图中不存在环称为有向无环图，简称DAG图
用DAG描述表达式
一图胜千言
拓扑排序性质及补充
时间复杂度：用到了栈
邻接矩阵O（|V|^2）
邻接表O（|V|+|E|）
性质（逆拓扑排序也一样）
拓扑排序不唯一
有向图拓扑排序有序，则邻接矩阵必是三角阵
有环一定不存在拓扑排序，所有拓扑排序常常用于判断是否有环
有环 = 有回路 = 有顶点数目大于1的强连通分量
邻接矩阵对角线以下皆为0
一定存在拓扑排序
拓扑排序不确定是否唯一，可能不唯一
例如
若邻接矩阵对角线上均为1，则拓扑排序唯一
拓扑排序唯一
不能唯一确定该图
不能说明各顶点入度、出度最多为1
一定能说明只有1个顶点入度为0，只有1个顶点出度为0
DFS序列唯一
不能唯一确定该图
有向图无回路
即使不使用访问标志位同一个结点也有可能访问2次
反例
两个拓扑排序相同却不一样的图
拓扑排序
定义
对于任何有向图而言，其拓扑排序为其所有节点的一个线性排序（对于同一个有向图而言可能存在多个这样的节点排序）。该排序满足这样的条件：对于图中的任意两个节点u和v，若存在一条有向边从u指向v，则在拓扑排序中u一定出现在v前面。
AOV网
用DAG图表示一个工程
顶点表示活动，边<vi,vj>表示vi在vj前
记法：Activitity On Vertex Network，因此顶点是活动
拓扑排序的实现
从AOV网中选择一个没有前驱（入度为0）的顶点并输出
从网中删除该顶点和所有以它为起点的有向边
重复上述操作至当前AOV网空 or 当前网中不存在无前驱的顶点为止（此时说明有环）
代码实现
用栈实现，实际上用队列实现也行
DFS实现
设置time变量为各顶点结束时间
DFS最后time ++,finishTime[v]=time;
将各结点结束时间按从大到小排序
逆拓扑排序
拓扑排序的入度为0改为出度为0
DFS实现：退栈前输出，也就是DFS代码最后的最后输出
相关思维导图模板
树图思维导图提供 一、研究内容 在线思维导图免费制作，点击“编辑”按钮，可对 一、研究内容 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：4f21797dd3e8b08f1951dfc24e7be94f
树图思维导图提供 904名中国成年人第三磨牙相关知识、态度、行为和病史的横断面调查 在线思维导图免费制作，点击“编辑”按钮，可对 904名中国成年人第三磨牙相关知识、态度、行为和病史的横断面调查 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：10b9a8a2dd2fb4593f8130ef16c320fc
沪公网安备 31011502019485号
上海工商