计算机知识路径应用思维导图
简单介绍路径应用的内容
树图思维导图提供 计算机知识路径应用思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 计算机知识路径应用思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：e30b6f410b9fd0c32228e089c1631b2c
思维导图大纲
路径应用思维导图模板大纲
最小生成树
算法
kruskal算法
时间复杂度：Elog2E,适合求解点稠图
prim算法
时间复杂度：V^2,适合求解边稠图
特点
当各边权值互不相等，生成树是唯一的
最短路径
dijkstra算法
不适用于含有负权值的边的图
单源最短路径时间复杂度：V^2
floyd算法
允许边带有负权值，但不能构成回路
把V0作为中间结点，若A[I][j]>A[i][0]+A[0][j]修改之，接下来V1、V2...
多源最短路径时间复杂度：V^3
BFS
适用于无权图
有向无环图（DAG）描述表达式
拓扑排序
AOV网：表示事件要发生的先后顺序，边的权值为1
拓扑排序步骤
每次找到一个入度为0的结点连同它发出的边删去
逆拓扑排序
每次找一个出度为0的结点和指向它的边删去
注意
若含有环，无法拓扑排序
邻接矩阵是三角矩阵，就存在拓扑排序
每个结点有唯一的前驱后继，才能使拓扑排序唯一
一个拓扑排序不能唯一确定一个图
有向图采用邻接表的拓扑排序时间复杂度为O（n+e）(2016)；邻接矩阵为O（n^2）
求关键路径算法本身不能判断是否有环，但第一步的拓扑排序能
AOE网：边的权值表示活动的持续时间
关键路径
结点表示事件，边表示活动
事件最早发生事件
由到结点的最长路径决定
事件最迟发生时间
从汇点回退
活动最早发生时间
等于弧头事件的最早发生时间
活动最迟发生时间
等于弧尾最晚发生时间-活动持续时间
活动事件余量
最迟-最早
关键活动的时间余量为0
特点
具有最大路径长度的路径是关键路径，路径上的活动是关键活动
只有缩短在所有关键路径上的关键活动才能缩短工期
延长关键路径一定延长工期
相关思维导图模板
树图思维导图提供 初中七年级需要掌握的信息技术基础知识 在线思维导图免费制作，点击“编辑”按钮，可对 初中七年级需要掌握的信息技术基础知识 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：44836e06aaf2236b0c1b008311fc3536
树图思维导图提供 作业帮思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 作业帮思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：0fa2dfe58ee459432166d72cafc50675
沪公网安备 31011502019485号
上海工商