数据结构第六章(下篇)
6.6 图的应用
6.6.1 最小生成树
-
生成树：所有顶点均由边连接在一起，但不存在回路的图
-
一个图可以有许多棵不同的生成树
-
所有生成树具有以下共同特点
- 生成树的顶点个数与图的顶点个数相同
- 生成树是图的极小连通子图，去掉一条边则非连通
- 一个有n个顶点的连通图的生成树有n-1条边
- 在生成树中再加一条边必然形成回路
- 生成树中任意两个顶点间的路径是唯一的
-
-
无向图的生成树：
- 设图G=(V,E)是个连通图，当从图任一顶点出发遍历图G时，将边集E(G)分成两个集合T(G) 和B(G)。其中 T(G)是遍历图时所经过的边的集合，B(G)是遍历图时未经过的边的集合。显然，G1(V,T)是图G的极小连通子图。即子图G1 是连通图G的生成树
-
最小生成树
-
给定一个无向网络，在该网络的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树，也叫最小代价生成树。
-
最小生成树的典型用途
- 要在n个城市间建立通信网，则n个城市应铺设n-1条路，每条路也有对应的经济成本
- 建立数学模型：
- 顶点 代表城市 有n个
- 边 代表线路 有n-1条
- 边的权值 表示线路的经济代价
- 连通网 表示n个城市间的通信网
-
-
构造最小生成树
- 构造最小生成树的算法很多，其中多数算法都利用了MST的性质
- MST性质：设N=（V,E) 是一个连通网，U是顶点集V的一个非空子集。若边(u,v) 是一条具有最小权值的边，其中$u\in U，v \in V-U$则必存在一棵包含边(u,v)的最小生成树
- 在生成树的构造过程中，图中n个顶点分属两个集合：
- 已落在生成树上的顶点集: U
- 尚未落在生成树上的顶点集: V-U
- 接下来则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边
6.6.1.1 普利姆(prim)算法
-
算法思想：
-
设N=（V,E)是连通网，TE是N上最小生成树 中边的集合
-
初始令$U={u_0}，(u_0 \in V),TE=${}
-
在所有$u\in U，v \in V-U$的边$（u,v）\in E$中找一条代价最小的边$(u_0,v_0)$.
-
将$(u_0,v_0)$并入集合TE，同时$v_o$并入U
-
重复上述操作直至U=V为止，则T=（V，TE）为N的最小生成树
-
6.6.1.2 克鲁斯卡尔(Kruskal)算法
- 算法思想：
- 设连通网 N=(VE)，令最小生成树初始状态为只有 n个顶点而无边的非连通图T=（V，{}),每个顶点自成一个连通分量。
- 在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上(即:不能形成环），则将此边加入到 T中;否则，舍去此边，选取下一条代价最小的边。
- 依此类推，直至T中所有顶点都在同一连通分量上为止。
- 最小生成树可能不唯一
| 算法名 | 普里姆算法 | 克鲁斯卡尔算法 |
|---|---|---|
| 算法思想 | 选择点 | 选择边 |
| 时间复杂度 | O（n^2)(n为顶点数) | O(eloge)（e为边数） |
| 适应范围 | 稠密图 | 稀疏图 |
6.6.2 最短路径
- 两种最常见的最短路径问题：
- 单源最短路径——用Dijkstra（迪杰斯特拉）算法
- 所有顶点间的最短路径——用Floyd——（弗洛伊德）算法
6.6.2.1 迪杰斯特拉算法
- 初始化：从源点$v_0$到各终点$v_k$的直达路径 $（v_o,v_k）$，即通过一条弧到达的路径。
- 选择：从这些路径中找出一条长度最短的路径$（v_0,u）$.
- 更新：然后对其余各条路径进行适当调整：
- 若在图中存在弧$(u，v_k)$,且$(v_0,u)+（u，v_k）<(v_0,v_k),则以路径（v_0,u,v_k）代替（v_0，v_k)$
- 在调整后的各条路径中，再找长度最短的路径，依此类推
时间复杂度为 $O(n^3)$
6.6.2.2 弗洛伊德算法
6.6.3 拓扑排序
-
有向无环图：无环的有向图，简称DAG图
- 有向无环图常用来描述一个工程或系统的进行过程。
- 一个工程可以分为若干个子工程，只要完成了这些子工程，就可以导致整个工程的完成
-
AOV网 拓扑排序
- 用一个有向图表示一个工程的各子工程及其相只制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称 AOV网(Activity On Vertex network)。
-
AOE网 关键路径
- 有向图表示一个工程的各子工程及其相互制约的关系，以弧表示活动，以顶点表示活动的开始或结束事件，称这种有向图为边表示活动的网，简称为AOE网 (Activity On Edge)
-
AOV网的特点：
- 若从i到j有一条有向路径，则i是j的前驱j是i的后继
- 若<i,j>是网中有向边，则i是j的直接前驱;j是i的直接后继
- AOV网中不允许有回路，因为如果有回路存在，则表明某项活动以自己为先决条件，显然这是荒谬的。
-
拓扑排序
- 在AOV 网没有回路的前提下，我们将全部活动排列成一个线性序列，使得若 AOV 网中有弧 <i,j>存在，则在这个序列中，i一定排在的前面，具有这种性质的线性序列称为拓扑有序序列，相应的拓扑有序排序的算法称为拓扑排序
-
拓扑排序方法：
- 在有向图中选一个没有前驱的顶点且输出
- 在图中删除该顶点和所有以他为尾的弧
- 重复1和2直到全部顶点均已输出；当图中不存在无前驱的顶点位置
- 一个AOV网的拓扑序列不是唯一的
-
拓扑排序的一个重要应用：
- 检测AOV网中是否存在环的方法：
- 对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该 AOV 网必定不存在环。
- 检测AOV网中是否存在环的方法：
-
关键路径
-
假设一个工程有11项活动，9个事件
- 事件V1——表示整个工程开始（源点：入度为0的顶点）
- 事件v9——表示整个工程结束（汇点：出度为0的顶点）
- 关键路径——路径长度最长的路径
- 路径长度——路径上各活动持续时间之和
- ve(vj)——表示事件vj的最早发生时间
- vl(vj)——表示事件vj的最迟发生时间
- e(i)——表示活动ai的最早开始时间
- l(i)——表示活动ai的最迟开始时间
- l(i)-e(i)——表示完成活动ai的时间余量
- 关键活动——关键路径上的活动，即l(i)==e(i)的活动（即没有时间余量的活动）
- 其中√的为关键活动，而包含关键活动的路径为关键路径
- 需要加快同时在几条关键路径上的关键活动
- 如：a11,a10,a8,a7
- 如果一个活动处于所有关键路径上，那么提高这个活动的速度，就能缩短整个工程的完成时间
- 如：a1,a4
- 处于所有关键路径上的活动完成时间不能缩短太多，否则会使原来的关键路径变成不是关键路径。这时必须重新寻找关键路径
- 需要加快同时在几条关键路径上的关键活动
相关推荐
评论