图的应用
最小生成树
普利姆（Prlm）
- ①从图中找第一个起始顶点v0，作为生成树的第一个顶点，然后从这个顶点到其他顶点的所有边中选一条权值最小的边。然后把这条边的另一个顶点v和这条边加入到生成树中。
- ②对剩下的其他所有顶点，分别检查这些顶点与顶点v的权值是否比这些顶点在lowcost数组中对应的权值小，如果更小，则用较小的权值更新lowcost数组。
- ③从更新后的lowcost数组中继续挑选权值最小而且不在生成树中的边，然后加入到生成树。
- ④反复执行②③直到所有所有顶点都加入到生成树中。
概要:
- 双重循环，外层循环次数为n-1，内层并列的两个循环次数都是n。故普利姆算法时间复杂度为O(n2)
而且时间复杂度只和n有关，所以适合稠密图
* 克鲁斯卡尔（Kruskal）
* 将图中边按照权值从小到大排列，然后从最小的边开始扫描，设置一个边的集合来记录，如果该边并入不构成回路的话，则将该边并入当前生成树。直到所有的边都检测完为止。
* 概要:
*
*
* 概要: 克鲁斯卡尔算法操作分为对边的权值排序部分和一个单重for循环，它们是并列关系，由于排序耗费时间大于单重循环，所以克鲁斯卡尔算法的主要时间耗费在排序上。排序和图中边的数量有关系，所以适合稀疏图最短路径
迪杰斯特拉
一个源点到其余顶点的最短路径
- 该算法设置一个集合S记录已求得的最短路径的顶点，可用一个数组s[]来实现，初始化为0，当s[vi]=1时表示将顶点vi放入S中，初始时把源点v0放入S中。此外，在构造过程中还设置了两个辅助数组：
dist[]：记录了从源点v0到其他各顶点当前的最短路径长度，dist[i]初值为arcsv0。
path[]：path[i]表示从源点到顶点i之间的最短路径的前驱结点，在算法结束时，可根据其值追溯得到源点v0到顶点vi的最短路径。
假设从顶点0出发，也就是顶点0为源点，集合S最初只包含顶点0，邻接矩阵arcs表示带权有向图，arcsi表示有向边<i，j>的权值，若不存在有向边<i，j>，则arcsi为∞。Dijkstra算法的步骤如下：
1）初始化：集合S初始为{0}，dist[]的初始值dist[i]=arcs0，i=1，2，…，n-1。
2）找出dist[]中的最小值dist[j]，将顶点j加入集合S，即修改s[vj]=1。
3）修改从v0出发到集合V-S上任一顶点vk可达的最短路径长度：如果dist[j] + arcsj< dist[k]，则令dist[k]=dist[j] + arcsj。另外更新path[k]=j(也就是顶点j加入集合之后如果有新的路径使得到顶点k路径变短的话就将到顶点k的路径长度修改成较短的)
4）重复2）～3）操作共n-1次，直到所有的顶点都包含在S中。
* 弗洛伊德
* 所有顶点到所有顶点的最短路径
* 算法思想：递推产生一个n阶方阵序列A(−1)，A(0)，…，A(k)，…，A(n−1)
其中A(k)i表示从顶点vi到顶点vj的路径长度，k表示绕行第k个顶点的运算步骤。初始时，对于任意两个顶点vi和vj，若它们之间存在边，则以此边上的权值作为它们之间的最短路径长度；若它们之间不存在有向边，则以∞作为它们之间的最短路径长度。以后逐步尝试在原路径中加入顶点k(k=0，1，…，n-1)作为中间顶点。如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径
* 非带权图
* 两点之间经过边数最少的路径
* 带权图
* 两点之间经过的边上权值之和最小的路径拓扑排序
AOV
- 如果我们把每个环节看成图中一个顶点，在这样一个有向图中，用顶点表示活动，用弧表示活动之间的优先关系，那么这样的有向图称为AOV网(Activity On Vertex)
- 拓扑排序就是对一个有向图构造拓扑序列的过程，构造会有两种结果：
如果此图全部顶点都被输出了，说明它是不存在回路的AOV网；
如果没有输出全部顶点，则说明这个图存在回路，不是AOV网。
* 拓扑排序算法：
从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为弧尾的弧。重复这个步骤直到输出图中全部顶点，或者找不到入度为0的顶点为止。
关键路径
- AOE(Activity On Edge):在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网称为AOE网。
