最小生成树
定义：生成树包含连通图的所有顶点，以及n-1条边。最小的含义是，边权和最小
性质：
1、最小生成树的树形不唯一。如果图的每条边权都互不相等的时候，该最小生成树的唯一的。
2、最小生成树的边权和是唯一的且最小的。
3、边数为顶点数-1
通用算法：
Prim算法：
1）从任意一个顶点开始，找该点相连的权值最小的边，加入到树T中。
2）从树T中已经得到的点中再找相连的权值最小的边，加入到树T中。
3）一直重复步骤2，直到生成一颗完整的树
时间复杂度：O(V^2)，在添加每个点的时候，都走一遍剩下来的点才能选出边权最小的点。不依赖于边长，主要是看点数。
Kruskal 算法：
根据总的边值来构建
1）先对所有的边根据权值进行排序
2）根据排序，选择相应的边的两个点组成连通分量。如果要选的两个点已经在同一个连通分量中，那么就下一条边
3）重复步骤2，直到生成完整的树
时间复杂度：O(ElogE)
边的总排序是O(Elog(E))，总的需要遍历所有的边，需要O(E)。在判断两个端点是否在一个连通分量中需要用到并查集，a(V)，整体为O(E)*a(V)。由于是顺序的，最高的复杂度为O(ElogE)。
最短路径
定义：一般计算带权最短路（如果是无权图，那么用BFS就可以写），一般有两种类型：一种是单源最短路：求图中某一顶点到其他各顶点的最短路径。另一种是每对顶点间的最短路径
通用算法：
Dijkstra 算法
不适用于带负权值的图，其他的最短路都可以算
算法步骤：
1）从初始值0开始出发，记S为已经选入的点，V为所有的点
2）从V-S中选出j，j满足当前源点到V-S（即剩余的点）中距离最短的点，并且把j加入到S中。
3）根据选出的j来更新源点到各个点的路径。（包括已经得到的点）
4）重复2-3直到选出所有的点。
时间复杂度：O(V^2)
Floyd算法
主要求两两顶点间的最短距离，可以允许负权值
这里直接上代码：
int d[N][N];
int n,m,k;
void Floyd(){
for(int k=1;k<=n;k++){//k为中间值
for(int v=1;v<=n;v++){
for(int v1=1;v1<=n;v1++){
//代表从v到v1之间距离的更新
d[v][v1]=min(d[v][k]+d[k][v1],d[v][v1]);
}
}
}
}
时间复杂度O(V^3)
有向无环图描述表达式
有向无环图：DAG
对应用树来存储表达式，图可以合并表达式相同的结点。
拓扑排序
AOV网：用DAG来存储一个工程，每个结点表示每个事件。只有当某个节点的入度为0，即不存在前驱节点的时候，才能进行该事件。
拓扑排序算法：
1、首先选择一个没有前驱节点的顶点入队列
2、输出队头，删除以该顶点为起点的有向边，并且把没有前驱节点的顶点入队
3、重复2，直到AOV网为空，或者不存在无前驱节点的顶点（说明存在环）
时间复杂度：邻接表 O(V+E)，邻接矩阵O(V^2)
上述的队列写法是BFS来实现，也可以通过栈即DFS来实现（先遍历，入栈的操作放在退出递归前，如果在递归前就输出了的话，就是逆拓扑排序）
如果一个AOV图存在拓扑排序，并且编号经过了从小到大的处理，对应的邻接矩阵一定是三角矩阵。
关键路径
定义：
首先关键路径存在于AOE网，即从普通的AOV网升级为AOE网，每条边加了权值，并且入度和出度为0的顶点都只有一个。
从开头到结尾的路径权值最大的路径，为关键路径。路径上的边成为关键活动。
需要找到关键路径，需要四个参数
1、事件（顶点）的最早发生时间ve(k)：即每个顶点最早可以开始的时间。（ min（是当前顶点的所有前驱+相应活动），取最大值的原因是只有当前驱节点的最后一个活动完成了，才能开始该事件）
2、事件的最晚发生时间 （从后向前推，为min(当前顶点的所有后驱节点-对应的活动) ，取最小值的原因是如果不去最小的，就会拖慢最后的进度）
3、活动（边）的最早开始时间。（和1相同，相当于最早）
4、活动的最晚开始时间。（边的终点最晚开始时间-边所需要花费的时间）
如果一个活动的3==4，那么该活动为关键活动，把所有的关键活动连接起来，就是关键路径。
注意点：
1、关键路径上的关键活动，如果延长关键活动的时间，一定会推迟最后的时间；如果缩短关键活动的时间，不一定会缩短时间，可能缩短了时间后，该路径不一定是关键路径
2、如果这个网的关键路径不唯一，只有对所有关键路径上的共同的关键活动缩短时间，才能缩短最后的时间
标签：路径,最小,时间,关键,应用,权值,顶点,408 From： https://www.cnblogs.com/yxdsTutorial/p/17379916.html