一、最小生成树
生成树:所有顶点均由边连接在一起,但不存在回路
一个图可以有多颗不同的生成树
生成树特点:生成树的顶点个数与图的顶点个数相同;
生成树是图的极小连通子图,去掉一条边则非连通,
一个有 n个顶点的连通图的生成树有 n-1 条边;
在生成树中再加一条边必然形成回路,
生成树两点之间路径是唯一的;
无向图生成树:深度优先遍历,广度优先遍历,遍历每个点
最小生成树:所有边权值之和最小
构造最小生成树:
MST贪心算法
普里姆(Prim)算法
把所有点分为A,B两个集合,任意选一个顶点a放到A集合,其余点放到B集合
选一个B集合中,到a权值最小的点b,放入A集合
再选一个B集合中,到a或者b权值最小的点,放入A集合 以此类推。
克鲁斯卡尔(Kruskal)算法
所有边按权值排序,依次把最小的边连上,不能形成回路否则舍去选取下一条边
两种算法比较
二、最短路径
两点间最短路径
迪杰斯特拉算法
求某一个顶点到其他顶点最短距离
先找直 达的最短路径,然后再找更短的路径替换
所有顶点间最短路径
弗洛伊德(Floyd)算法
逐个加顶点试探
三、有向无环图
AOV网:
AOE网:
四、拓扑排序
针对有向无环(DAG)图 AOV网
方法
在有向图中选一个没有前驱的顶点且输出。
从图中删除该顶点和所有以它为尾的弧。
重复上述两步,直至全部顶点均已输出;或者当图中不存在无前驱的顶点为止
拓扑序列不唯一
作用
检测AOV网中是否存在环
五、关键路径
针对有向无环(DAG)图 AOE网
源点:入度为0的顶点
汇点:出度为0的顶点
对于AOE网,关心两个问题
完成整项工程至少需要多少时间?
哪些活动是影响工程进度的关键?
关键路径 -- 路径长度最长的路径,
路径长度 -- 路径上各活动持续时间之和
几个描述量
ve(vj)-- 表示事件 vj 的最早发生时间。
v(vj)-- 表示事件 vj 的最迟发生时间。
e(i) -- 表示活动 ai 的最早开始时间
I(i)-- 表示活动 ai 的最迟开始时间
I(i)- e(i) -- 表示完成活动(ai 的时间余量
关键活动 -- 关键路径上的活动,即|(i) == e(i)(即|(i)-e(i)==0 )的活动。
标签:10,--,路径,生成,算法,集合,顶点,数据结构 From: https://blog.csdn.net/2301_79600945/article/details/141936956