一、最小生成树
生成树:所有的顶点都由边连接在一起，但是不存在回路的图;
- 既要连通，又不存在回路
- 图可以有多个不同的生成树
- 生成树的特点
- 生成树的顶点个数与图的顶点相同
- 生成树是图的极小连通子图，去掉一条边则不连通
- 一个有n个顶点的连通图的生成树有n-1条边
- 在生成树多加一条边必定行程回路
- 任意两顶点路径唯一
- 含有n个顶点的n-1条边的图不一定是生成树!
1. 无向图的生成树
广度优先生成树
2. 最小生成树
- 给定一个无向的网，那么在该网的所有生成树中，有各边权值之和最小的那颗生成树，则称之为该网的最小生成树，也叫最小的代价树；
典型的用途
Eg: n个城市之间建立通讯网，n个就需要应铺n-1条线路。
3. MST的性质
4. prim算法
设计思路
- 设N=(V,E)连通图，TE是N上的一个最小生成树边的集合
- 初始化
- U={u0},TE=空
- 选出u>U到v>V-U集合顶点之间一条权值最小的边
- 将边并入到集合TE
- 同时v0并入U
- 重复上述操作，直到U==V为止;
就是每次去找一个顶点 ，和V-U集合当中顶点的一起的边权值最小
5. Kruskal算法
设计思路
- 设立一个只有n个顶点无边的非连通图T=(V,{})，每个顶点自成一个连通分量
- 在所有边当中选权最小的边
- 若加入之后没有形成环，则加入T
- 否则舍去,选择下一个最小的边
- 重复操作: 直接所有的顶点都在同意连通分量当中为止
二、最短路径
典型的应用2
在有向网当中，从源点到终点当中，寻找各边权和最小。就是最短路径。
交通网络问题
- 交通网络使用有向网表示
- 顶点表示地点
- 弧表示两个地点的连通
- 权值表示两地点的距离，花费的时间等。
从源点到终点，寻找一条权值之和最小的路径，就是最短路径
第一类(单源路径)
- 使用Dijkstra算法
- 寻找两点/之间路径最短问题
第二类
- Floyd算法
- 某个源点到其他个点最短路径
Dijkstra算法(ReView)
有效的程序员，不应该浪费时间用于程序调试，他们应该一开始就不把故障引入。
算法思想
- 初始化
- 先找出V源点到K终点的直达路径
- 若能直达
- 记录
- 若不能直达
- 记录为无穷
- 若能直达
- 先找出V源点到K终点的直达路径
- 选择
- 从这些路径中找出长度最短的路径(V0,u)
更新
- 对于其余的路径进行适当调整
- 若图中存在(u0,vk),切(v0,u)+(u,vk)<(v0,vk)
- 则用(V0,u,Vk)代替(V0,Vk);
调整之后，在找长度最短的路径，依次类推。
- 对于其余的路径进行适当调整
c语言实现
Floyd算法
引入
求出所有顶点之间的最短路径?
Mthod1:
还用Dijkstra算法,以每个顶点为源,重复执行O(n^3)
Mthod2:
使用弗洛伊德的算法
算法思想
- 逐个顶点试探
- 找出从vi-vj所有可能存在的路径
- 选择出最短路径
咋子
三、拓扑排序
有向无环图的应用
没有回路的图
- 若i到j有一条有向路径，则i是j的前驱，j是i的后继
- 若
- AOV网当中，不能有回路
如果判断AOV网中是否存在回路？（拓扑排序)
- 将一个拓扑图，边换成一个拓扑序列(线性序列)的算法
排序的方法##
- 找一个没有前驱的顶点，直接输出
- 从图中删除该顶点和所有以它为弧尾的弧
- 重复上述两部，直到全部定点都输出，或者图当中不存在无前驱顶点位置
练习
- 写出该拓扑图的拓扑序列
AOV网的拓扑序列不唯一 拓扑图的拓扑有序序列，若所有顶点都在它的拓扑有序序列中，则AOV网必定不存在环
四、关键路径
从源点到汇点，路径长度最长的路径
AOE网
关键路径
- 弧来表示活动
顶点表示开始和结束的事件
求解关键路径
我们先定义4个描述量
- ve(vj)表示事件最早发生的时间。
- 例如，ve(v1)最早的发生时间是0
- ve(v2)最早的发生时间是 30
- vl(vj)表示事件vj的最晚发生时间
- e(i)表示ai的最早开始时间
- e(a3) = 30
- l(i)表示活动ai最晚发生的时间
l(i)-e(i) —- 表示时间的余量
关键活动
- 时间余量为0的活动
由关键活动组成起来的路径就是关键路径
如何求关键活动?
关键方法与步骤
- 求出 ve(i) 、vl(j)
- 求出e(i) 、l(i)
计算出l(i) - e(i)
求出下列的关键路径
若有收获，就点个赞吧
0 人点赞
