图的应用（408）-526互联

最小生成树

定义：生成树包含连通图的所有顶点，以及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]);
            }
        }
    }
}