数据结构-图的笔记(4)（图的最小生成树和最短路径）
目录
生成树
构造最小生成树方法二：克鲁斯卡尔（）算法
补充两种算法的比较
最短路径
（迪杰斯特拉）算法
Floyd（弗洛伊德）算法
生成树
生成树：所有顶点均由边连接在一起，但不存在回路的图。
一个图可以有许多棵不同的生成树
所有生成树具有以下共同特点：
1.生成树的顶点个数与图的顶点个数相同。
2.生成树是图的极小连通子图，去掉一条边则非连通。
3.一个有n个顶点的连通图的生成树有n-1条边。
4.在生成树中再加一条边必然形成回路。
5.生成树中任意两个顶点间的路径是唯一的。
最小生成树（最小生成树可能不唯一）：给定一个无向网络，在该网的所有是生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树，也叫做最小代价生成树。
如下图所示：各边权值之和=17的是最小生成树。
构造最小生成树的算法很多，其中多数算法都利用了MST的性质。
MST性质：设N=（V,E）是一个连通网，U是顶点集V的一个非空子集。若边（u，v）是一条具有最小权值的边，其中u属于U，v属于V-U，则必存在一棵包含边（u，v）的最小生成树。
MST性质解释：在生成树的构造过程中，图中n个顶点分属两个集合：已落在生成树上的顶点集：U，尚未落在生成树上的顶点集：V-U。
接下来则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。
构造最小生成树方法一：普利姆（Prim）算法
算法思想：
1.设N=（V,E）是连通网，TE是N上最小生成树中边的集合。
2.初始令U={u0},(u0属于V)，TE={}。
3.在所有u属于U，v属于V-U的边且（u，v）属于E中，找一条代价最小的边(u0,v0)。
4.将（u0,v0）并入集合TE，同时v0并入U。
5.重复上述操作直至U=V为止，则T=（V,TE）为N的最小生成树。
最小生成树为图中蓝色颜色路径如下图所示：
构造最小生成树方法二：克鲁斯卡尔（）算法
算法思想：
1.设连通网N={V，E}，令最小生成树初始状态为只有n个顶点而无边的非连通图T={V,{}}，每个顶点自成一个连通分量。
2.在E中选取代价最小的边，若该边依附的顶点落在T在不同的连通分量（即：不能形成环），则将此边加入到T中；否则，舍弃此边，选取下一条代价最小的边。
3.依此类推，直至T中所有顶点都在同一连通分量上为止。
最小生成树为图中蓝色颜色路径如下图所示：
补充两种算法的比较
最短路径
最短路径：在有向网中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。
最短路径与最小生成树不同，路径上不一定包含n个顶点，也不一定包含n-1条边。
常见的最短路径问题：
一、单源最短路径-用（迪杰斯特拉）算法
二、所有顶点间的最短路径-用Floyd（弗洛伊德）算法
（迪杰斯特拉）算法
算法思想：
1.初始化：先找出从源点v0到各终点vk的直达路径（v0,vk）,即通过一条弧到达的路径。
2.选择：从这些路径中找到一条长度最短的路径（v0,u）。
3.更新：然后对其余路径进行适当调整：
若在图中存在弧/边（u,vk），且（v0,u）+（u,vk）小于（v0,vk），则以路径（v0,u,vk）代替（v0,vk）。
4.在调整后的各条路径中，再找长度最短的路径，依此类推。
迪杰斯特拉（）算法：按路径长度递增次序产生最短路径。
算法分析：
1.把V分成两组：
（1）S：已求出最短路径的顶点的集合。
（2）T=V-S：尚未确定最短路径的顶点集合。
2.将T中顶点按最短路径递增的次序加入到S中，
保证：（1）从源点v0到S中各顶点的最短路径长度都不大于从v0到T中任何点的最短路径长度。
(2)每个顶点对应一个距离值：
S中的顶点：从v0到此顶点的最短路径长度。
T中的顶点：从v0到此顶点的只包括S中顶点做中间顶点的最短路径长度。
算法步骤：
1.初始时令S={v0},T={其余顶点}。
2.T中顶点对应的距离值使用辅助数组D存放，D[i]初值：若存在，则为其权值；否则为无穷大。
3.从T中选取一个其距离值最小的顶点vj，加入S。
4.对T中顶点的距离值进行修改：若加进vj做中间顶点，从v0到vi的距离值比不加vj的路径要短，则修改此距离值。重复上述步骤，直到S=V为止。
Floyd（弗洛伊德）算法
算法思想：
1.逐个顶点试探。
2.从vi到vj的所有可能存在的路径中，选出一条长度最短的路径。
最短路径步骤：
1.初始时设置一个n阶方阵，令其对角线元素为0，若存在弧，则对应元素为权值；否则为无穷大。
2.逐步试着在原直接路径中增加中间顶点，若加入中间顶点后路径变短，则修改之；否则，维持原值。所有顶点试探完毕，算法结束。
求最短路径过程如下图所示：
