图的应用（最小生成树，最短路径，有向无环图）

一.最小生成树

1.生成树

2.无向图的生成树

3.最小生成树算法

二.最短路径

1.单源最短路径---Dijkstra（迪杰斯特拉）算法

2.所有顶点间的最短路径---Floyd（弗洛伊德）算法

三.有向无环图的应用

1.AOV网（拓扑排序）

2.AOE网（关键路径）

一.最小生成树

1.生成树

所有顶点均有边连接在一起，但不存在回路的图

•一个图可以有许多棵不同的生成树

•所有生成树都具有以下共同特点

         •生成树的顶点个数与图的顶点个数相同

         •生成树是图的极小连通子图，去掉一条边则非连通

         •一个有n个顶点的连通图的生成树有(n-1)条边

         •在生成树中再加一条边必然形成回路

•生成树中任意两个顶点间的路径是唯一的

•含n个顶点n-1条边的图不一定是生成树

2.无向图的生成树

无向图的生成树可以与深度优先搜索遍历与广度优先搜索遍历的方法结合起来

不了解的可以看看这篇

深度优先搜索遍历与广度优先搜索遍历

深度优先生成树：V1->V2->V4->V8->V5->V3->V6->V7

广度优先生成树：V1->V2->V3->V4->V5->V6->V7->V8

3.最小生成树算法

给定一个无向网络，在该网所有的生成树中，使得各边权值之和最小的那棵生成树称为最小生成树，也叫最小代价生成树

生成最小生成树的方法

MST(Minimum Spanning Tree)

•已落在生成树上的顶点集：U

•尚未落在生成树的顶点集：V-U

•选取权值最小的边，因为权值最小的边一定存在生成树是包含他的

（1）普里姆（Prim）算法

•设N=(V,E)是连通网，TE是N上最小生成树中边的集合
•初始令 U={u0},(u0 $\in$ V)， TE={}

•在所有 u $\in$ U, v $\in$ V-U的边(u v) $\in$ E中，找条代价最小的边(u0，v0)

•将(u0,v0)并入集合 TE，同时v0并入 U

（2）克鲁斯卡尔（Kruskal）算法

•设连通网 N=(V，E)，令最小生成树初始状态为只有 n个顶点而无边的非连通图T=(V，{})，每个顶点自成一个连通分量。

•在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上(即:不能形成环），则将此边加入到 T中;否则，舍去此边，选取下一条代价最小的边。
•依此类推，直至T中所有顶点都在同一连通分量上为止。

（3）两种算法的区别

•普里姆算法是选择点，从U集合到V-U集合找一条权值最小的边，将这个边连接的点加入到U集合中，而克鲁斯卡尔算法则是在所有边中找权值最小的边，加入到生成树中，直到所有的点连通，边为n-1条。

•普里姆算法的时间复杂度为O( $n^{2}$ ),对于所有的点，都需要遍历其他顶点进行判断下一个加入生成树的点，克鲁斯卡尔算法则是选择边，和顶点数无关，只跟边数有关，对顶点的权值进行排序时，平均情况是(eloge)

•克鲁斯卡尔算法时间复杂度只跟边数有关，所以边数较少时，算法时间较少，所以克鲁斯卡尔算法适用于稀疏图，普里姆算法适用于稠密图。

二.最短路径

在有向网中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径

最短路径与最小生成树不同，路径上不一定包含n个顶点，也不一定包含n-1条边

•两点间的最短路径

下图最短路径值为14

•某源点到其他各点最短路径

1.单源最短路径---Dijkstra（迪杰斯特拉）算法

算法步骤

•初始时令S={v0},T={其余顶点}

•T中顶点对应的距离值用辅助数组D存放

•D[i]初值：若<v0, $v_{i}$ >存在，则为权值；否则为 $\bowtie$

•从T中选取一个其距离值最小的顶点 $v_{j}$ ,加入S

•对T中顶点的距离值进行修改：若加进 $v_{j}$ 作中间顶点，从v0到 $v_{i}$ 的距离值比不加 $v_{j}$ 的路径要短，则修改此距离值。

•重复上述步骤，直到S=V为止

以下图为例

Dijkstra（迪杰斯特拉）算法可以计算1个顶点到其他顶点的最短路径，时间复杂度为O( $n^{2}$ )

如果要计算所有顶点间的最短路径，即O( $n^{2}$ )*n=O( $n^{3}$ )

2.所有顶点间的最短路径---Floyd（弗洛伊德）算法

算法步骤

•逐个顶点试探

•从vi到vj的所有可能存在的路径中

•选出一条长度最短的路径

初始设置一个n阶方阵，令其对角线元素为0,若存在弧<vi,vj>,则对应元素为权值；否则为 $\bowtie$

如图：A-->B的权值为4,B-->A的权值为6，以此类推，可得n阶方阵

加入A顶点，如图，本来C--->B没有路径（ $\bowtie$ ），但是可以从C-->A--->B,路径长度为7

加入B，如图，原来A--->C为11，现在加入B，变为A--->B--->C,变得更小了，所以6替换11

加入C，如图，B--->A路径长度为6，B--->C--->A路径长度变短，所以5替换6

以上总结为：逐步试着在原直接路径中增加中间顶点，若加入中间顶点后路径变短，则修改之;否则，维持原值。所有顶点试探完毕，算法结束。