最小生成树
最短路径
拓扑排序
关键路径
最小生成树
➢一个图可以有许多棵不同的生成树
➢所有生成树具有以下共同特点
生成树的顶点个数与图的顶点个数相同;
生成树是图的极小连通子图，去掉一条边则非连通;
一个有n个顶点的连通图的生成树有n-1条边;
在生成树中再加一条边必然形成回路。
➢含n个顶点n-1条边的图不一定是生成树。
设图G=(V, E)是个连通图，当从图任一顶点出发遍历图G 时，将边集E(G)分成两个集合T(G)和B(G)。其中T(G)是遍历图时所经过的边的集合，B(G) 是遍历图时未经过的边的集合。显然，G1(V,T) 是图G的极小连通子图。即子图G1是连通图G的生成树。
最小生成树
最小生成树:给定- -个无向网络，在该网的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树，也叫最小代价生成树。
构造最小生成树
构造最小生成树Minimum Spanning Tree
构造最小生成树的算法很多,其中多数算法都利用了MST的性质。
MST性质:设N= (V, E)是一个连通网，U是顶点集V的一个非空子集。若边(u,v)是一条具有最小权值的边，其中u∈U, v∈V-U,则必存在一棵包含边(u, v)的最小生成树。
构造最小生成树方法一-: 普里姆(Prim)算法
算法思想:
➢设N=(V, E)是连通网，TE是N上最小生成树中边的集合。
➢初始令U={Uo}, (Ug∈V), TE={}。
➢在所有ueU, VE V-U的边(u, v∈E中，找一条代价最小的边(Uo, v)。
➢将(Uo, v)并入集合TE,同时v并入U。
➢重复上述操作直至U=V为止，则T=(V, TE) 为N的最小生成树。
构造最小生成树方法二:克鲁斯卡尔(Kruskal) 算法。
算法思想:
设连通网N= (V E),令最小生成树初始状态为只有n个顶点而无边的非连通图T=(V {}),每个顶点自成一个连通分量。
➢在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上(即:不能形成环) ,则将此边加入到T中;否则，舍去此边，选取下一条代价最小的边。依此类推，直至T中所有顶点都在同一连通分量.上为止。
最短路径
问题抽象:在有向网中A点(源点)到达B点(终点)的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。最短路径与最小生成树不同，路径上不一定包含n个顶点，也不一定包含n- 1条边。
两种常见的最短路径问题:
一、单源最短路径一 用Diikstra (迪杰斯特拉)算法
二、所有顶点间的最短路径一-用Floyd (弗洛伊德)算法
Dijistra算法
1.初始化:先找出从源点v。到各终点vk的直达路径(Vo,Vk) ,即通过一条弧到达的路径。
2.选择:从这些路径中找出一条长度最短的路径(Vo,u) 。
3.更新:然后对其余各条路径进行适当调整:
若在图中存在弧(u,vk) ，且(Vo,u) + (u,Vk) < (Vo,vk) ，则以路径(Vo,U,Vk) 代替(Vo,Vk) 。
在调整后的各条路径中，再找长度最短的路径，依此类推。
迪杰斯特拉(Dijkstra)算法:按路径长度递增次序产生最短路径
1、把V分成两组:
(1) S:已求出最短路径的顶点的集合。
(2) T=V -S :尚未确定最短路径的顶点集合。
2、将T中顶点按最短路径递增的次序加入到S中
保证: (1) 从源点V到S中各顶点的最短路径长度都不大于从Vo到T中任何顶点的最短路径长度。
(2)每个顶点对应一-个距离值:S中顶点:从Vo到此顶点的最短路径长度。T中顶点:从Vo到此顶点的只包括S中顶点作中间顶点的最短路径长度。
Dijkstra算法步骤:
初始时令S={Vo}, T={其余顶点}。T中顶点对应的距离值用辅助数组D存放。D[]初值:若<V, V;> 存在，则为其权值;否则为∞。从T中选取一个其距离值最小的顶点V;加入S。对T中顶点的距离值进行修改:若加进v;作中间顶点，从V到V;的距离值比不加V;的路径要短，则修改此距离值。重复上述步骤，直到S = V为止。
拓扑排序&关键路径
有向无环图简称DAG图Direction Cyclical Grapt
有向无环图常用来描述一个工程或系统的进行过程。(通常把计划施工、生产、程序流程等当成是一个工程)
一个工程可以分为若干个子工程，只要完成了这些子工程(活动)就可以导致整个工程的完成。
AOV网（解决拓扑排序）:
用一-个有向图表示一-个工程的各子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称AOV网(Activity On Vertex network)。
AOV网的特点:
1、若从i到j有一条有向路径，则i是j的前驱;j是i 的后继。
2、若< i,j>是网中有向边，则i是j的直接前驱;j是 i的直接后继。
3、AOV 网中不允许有回路,因为如果有回路存在，则表明某项活动以自己为先决条件，显然这是荒谬的。
拓扑排序
在AOV网没有回路的前提下，我们将全部活动排列成一个线性序列，使得若AOV网中有弧<i, j>存在，则在这个序列中，i 一定排在j的前面，具有这种性质的线性序列称为拓扑有序序列，相应的拓扑有序排序的算法称为拓扑排序。
拓扑排序的方法:
1、在有向图中选一一个没有 前驱的顶点且输出之。
2、从图中删除该顶点和所有以它为尾的弧。
3、重复上述两步，直至全部顶点均已输出;或者当图中不存在无前驱的顶点为止
拓扑序列:
C1,C2, C3,C4, C5, C7, C9, C10, C11,C6, C12, C8
C9, C10, C11, C6, C1, C12, C4, C2,C3, C5, C7, C8
一 个AOV网的拓扑序列不是唯一 的
拓扑排序的一个重要应用:
检测AOV网中是否存在环方法:
对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。
AOE网（解决关键路径）:
用一个有向图表示一个工程的各子工程及其相互制约的关系，以弧表示活动，以顶点表示活动的开始或结束事件，称这种有向图为边表示活动的网，简称为AOE网(Activity On Edge) 。
关键路径
把工程计划表示为边表示活动的网络，即AOE网，用顶点表示事件，弧表示活动，弧的权表示活动持续时间。
事件表示在它之前的活动已经完成，在它之后的活动可以开始。
对于AOE网，我们关心两个问题:
(1)完成整项工程至少需要多少时间?
(2)哪些活动是影响工程进度的关键?
关键路径一路径长度最长的路径。
路径长度一路径 上各活动持续时间之和。
求关键路径步骤:
1.求ve(i)、 vl(j)
2.求e(i)、 l(i)
3.计算|(i)-e(i)
