生成树及其构造
生成树：所有顶点均由边连接在一起，但不存在回路的图
所有生成树具有以下共同特点：
①生成树的顶点个数与图的顶点个数相同
②生成树是图的极小联通子图，去掉一条边则非连通
③一个有n个顶点的连通图的生成树有n-1条边
④在生成树中再加一条边必然形成回路
⑤生成树中任意两个顶点间的路径是唯一的
含n个顶点n-1条边的图不一定是生成树
无向图的生成树：
最小生成树
定义：给定一个无向网络，在该网的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树，也叫最小代价生成树
构造最小生成树（Minimun Spanning Tree）:
设N=(V,E)是一个连通网，U是顶点集V的一个非空子集，若边(u,v)是一条最小权值的边，其中u∈U，
v∈V-U，则必存在一棵包含边(u,v)的最小生成树
MST性质解释：
在生成树的构造过程中，图中n个顶点分属两个集合：
①已落在生成树上的顶点集U
②尚未落在生成树上的顶点集V-U
接下来则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边
构造最小生成树方法一：普里姆（Prim）算法
算法思想：
①设N=(V,E)是联通网，TE是N上最小生成树中边的集合
②初始令U={u0}，(u0∈V)，TE={}
③在所有u∈U，v∈V-U的边(u,v)∈E中，找一条代价最小的边(u0,v0)
④将(u0,v0)并入集合TE，同时v0并入U
⑤重复上述操作直至U=V为止，则T=(V,TE)为N的最小生成树
构造最小生成树方法二：克鲁斯卡尔（Kruskal）算法
算法思想：
①设连通网N=(V,E)，令最小生成树初始状态只有n个顶点而无边的非连通图T={V,{}}，每个顶点自成一个连通分量
②在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上（即不能形成环），则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边
③以此类推，直至T中所有顶点都在同一连通分量上为止
最短路径
典型用途：交通网络的问题——从甲地到乙地之间是否有公路连通？在有多条通路的情况下，哪一条路最短？
交通网络用有向图来表示：
顶点——表示地点
弧——表示两个地点有路连通
弧上的权值——表示两地点之间的距离，交通费或途中所花费的时间等
问题抽象：在有向网中A点（源点）达到B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最
短路径（最短路径与最小生成树不同，路径上不一定包含n个顶点，也不一定包含n-1条边）
两种常见的最短路径问题：
（1）单源最短路径——用Dijkstra（迪杰斯特拉）算法
①初始化：先找出从源点v0到各终点vk的直达路径（v0,vk）,即通过一条弧达到的路径
②选择：从这些路径中找出一条长度最短的路径（v0,u）
③更新：然后对其余各条路径进行适当调整
若在图中存在弧(u,vk)，且(v0,u)+(u,vk)<(v0,vk)，则以路径(v0,u,vk)代替(v0,vk)
在调整后的各条路径中，再找长度最短的路径，依次类推
迪杰斯特拉算法：按路径长度递增次序产生最短路径
1）把V分成两组
①S：已求出最短路径的顶点的集合
②T=V-S：尚未确定最短路径的顶点集合
2）将T中顶点按最短路径递增的次序加入到S中，保证：
①从源点v0到S中各顶点的最短路径长度都不大于从v0到T中任何顶点的最短路径长度
②每个顶点对应一个距离值：
S中顶点：从v0到此顶点的最短路径长度
T中顶点：从v0到此顶点的只包括S中顶点作中间顶点的最短路径长度
（2）所有顶点间的最短路径——用Floyd（弗洛伊德）算法
算法思想：
①逐个顶点试探
②从vi到vj的所有可能存在的路径中选出一条长度最短的路径
求最短路径步骤：
①初始时设置一个n阶方阵，令其对角线元素为0，若存在弧
②逐步试着在原直接路径中增加中间顶点，若加入中间顶点后路径变短，则修改之；否则，维持原值。所有顶点试探完毕，算法结束
有向无环图及其应用
有向无环图：无环的有向图，简称DAG图（Directed Acycline Graph）
（1）AOV网（拓扑排序）：用一个有向图表示一个工程的各子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称AOV网（Activity On Vertex network）
AOV网的特点：
①若从i到j有一条有向路径，则i是j的前驱，j是i的后继
②若
③AOV网中不允许有回路，因为如果有回路存在，则表明某项活动以自己为先决条件，显然这是荒谬的
拓扑排序：在AOV网没有回路的前提下，我们将全部活动排列成一个线性序列，使得若AOV网中有弧
拓扑排序的方法：
①在有向图中选一个没有前驱的顶点且输出之
②从图中删除该顶点和所有以它为尾的弧
③重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止
检测AOV网中是否存在环的方法：
对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环
AOE网（关键路径）：用一个有向图表示一个工程的各子工程及其相互制约的关系，以弧表示活动，以顶点表示活动的开始或结束事件，称这种有向图为边表示活动的网，简称AOE网（Activity On Edge）
关键路径：把工程计划表示为边表示活动的网络，即AOE网，用顶点表示事件，弧表示活动，弧的权表示活动持续时间（路径长度最长的路径）
路径长度：路径上各活动持续时间之和
确定关键路径，需要定义4个描述量：
①ve(vj)——表示事件vj的最早发生时间
②vl(vj)——表示事件vj的最迟发生时间
③e(i)——表示活动ai的最早开始时间
④l(i)——表示活动ai的最迟开始时间
l(i)-e(i)——表示完成活动ai的时间余量
关键活动——关键路径上的活动，即l(i)=e(i)的活动
如何找关键活动：
设活动ai用弧
则有：①e(i)=ve(j)
②l(i)=vl(k)-wj,k
如何求ve(j)和vl(j)：
①从ve(1)=0开始向前递推，ve(j)=Max{ve(i)+wi,j},
②从vl(n)=ve(n)开始向后递推，vl(i)=Min{vl(j)-wi,j},
若有收获，就点个赞吧
0 人点赞
