生成树

极小连通图

我们来讨论一下极小连通子图。这里的极小主要是说的边数的极小，首先依然要是原图的子图并且是连通的，但是此时要求具有最大的顶点数和最小的边数，也就是说再去掉任意一条边会导致图不连通（直接理解为极大连通子图尽可能去掉能去掉的边就行了）

针对于极小连通子图，我们一般只讨论无向图我们依然将原图就是连通图和原图不是连通图分开分析，首先是原图本身就是连通图的情况：
示意图
原图本身就是连通图，那么其极大连通子图就是其本身，此时我们需要尽可能去掉那些“不必要”的边，依然能够保证其是连通的，也就是极小连通子图。可以看到右边两幅图，跟左边这幅图包含了同样的顶点数量，但是边数被去掉了一些，并且如果再继续去掉任意一条边的话，那么就会导致不连通，所以说左边两幅图都是右边这幅图的极小连通图（当然，就像上面这样，可能会出现多种方案，极小连通图不唯一）

我们发现，无论是去掉哪些边的情况，到最后一定是只留下 N-1 条边（其中N是顶点数）每个顶点有且仅有一条路径相连，也就是包含原图全部N个顶点的极小连通子图，我们一般称其为：生成树，为什么叫生成树呢，因为结点数和边数正好满足树的定义（且不存在回路的情况），我们可以将其调整为一棵树：
示意图
当然，这是原图本身就连通的情况，如果原图本身不连通的话，那么就会出现多个连通分量，此时就会得到一片生成森林，森林中的树的数量就是其连通分量的数量。

如何得到有向图生成树

那么我们在程序中要怎么才能得到一个有向图的生成树呢？我们可以使用前面讲解的两种图的遍历方式来进行生成，我们以下图为例，这是一个普通的无向连通图：
示意图
我们如果按照深度优先遍历的方式，从G开始，那么就会得到下面的顺序：
示意图
按照顺序我们就可以得到一棵生成树：
示意图
同样的，我们来看看如果是按照广度优先遍历的方式，又会得到什么结果呢？
示意图
最后得到的生成树为：
示意图
因为深度优先遍历和广度优先遍历本身的顺序就不是唯一的，所以最后得到的生成树也不是唯一的。

最小生成树

什么是最小生成树

生成树讨论完成之后，我们接着来讨论一下最小生成树，那么这个最小指的是什么最小呢？如果我们给一个无向图的边都加上权值（网图）现在要求生成树边的权值总和最小，我们就称这棵树为最小生成树（注意最小生成树不唯一，因为有可能出现多种方案都是最小的情况）比如下面的就是最后得到的最小生成树了：
示意图
构建最小生成树有两种算法，一种是普利姆（Prim）算法，还有一种是克鲁斯卡尔（Kruskal）算法，我们先来讨论第一种。

普利姆（Prim）算法

我们以下图为例：
示意图
普利姆算法的核心就是从任意一个顶点开始，不断成长为一棵树，每次都会选择尽可能小的方向去进行延伸，比如我们一开始还是从顶点A开始。

此时与A相连的边有B和E，A的延伸方向有两个，此时我们只需要选择一个最小的就可以了：
示意图
此时我们已经构建出了由A、E组成的一棵树，同样的，我们需要去寻找与当前树中A、E顶点相连的所有顶点，包括B、G、H，哪一个最小，那么下一个延伸的就是哪一个，此时发现H和E之间最小，继续延伸：
示意图
现在已经变成了由A、E、H组成的一棵树，同样的，按照之前的思路继续寻找一个最小的方向进行延伸：
示意图
继续进行延伸，发现F、K之间最小：
示意图
此时K、B和K、D和K、H的权重都是4，其中H顶点已经走过了，不能出现回路，所以说不考虑，此时随便选择K、B或是K、D都可以，不会影响后续结果：
示意图
此时依然是K、D为最小，所以说直接选择：
示意图
紧接着，我们发现最小权重的来到了5，此时权重为5的边有B、E和H、I和B、D，但是由于E、D已经走过，此时直接选择H、I即可：
示意图
接着，我们发现I、G也是5，直接选择即可：
示意图
然后最小权重此时就是6了，选择H、J和I、J都可以，随便选择一个即可：
示意图
此时，整个图的所有顶点就遍历完成了，现在我们去掉那些没用被采用的边，得到的结果就是我们的最小生成树了：
示意图

克鲁斯卡尔（Kruskal）

我们接着来看另一种，克鲁斯卡尔算法，它的核心思想就是我们主动去选择那些小的边，而不是像上面一样被动地扩展延伸。

在一开始的时候，直接去掉所有的边，我们从这些边中一个一个选择出来（注意是任意一条边都可以选择，并不是只有选择的顶点旁边才能选择，这个过程中可能会出现多棵树，但是最后一定会连成一棵树的），最后形成一颗最小生成树，假设一开始什么都没选择，被选中的边我们一会用橙色标注：
示意图
首先我们直接找到最小边，K、F，它的权值为2，所以说直接选择就行：
示意图
此时最小的权重就只有4了，目前有4条边都可以进行选择，但是K、H这条边因为K和H都已经在树中了，所以说不能考虑，其他三条边都是没问题的，我们随便选择一条就行了：
示意图
继续选择权重为4的边：
示意图
此时权重就来到了5，那么权重为5的顶点我们也可以随便选择一条，只要不会导致出现回路就行了：
示意图
此时连接G、I，我们发现出现了两棵树，没关系的，最后会连成一棵树的，我们继续选择其他权重为5的边：
示意图
此时我们选择A、E这条边，然后是H、I这条边，虽然这条边上的H和I顶点都已经在树中了，但是它们并不属于同一棵树，这种情况也是可以连接的，然后我们继续选择权重为6的顶点：
示意图
此时选择I、J或是H、J都可以（最小生成树不唯一）现在我们已经连接上所有的顶点了，最小生成树构建完成，我们把那些没有选择都边都扔了：
示意图
其实无论是哪种算法，最后都能够得到一棵最小生成树，有关实现代码，由于太过复杂，这里就不进行编写了。

最短路径问题

前面我们介绍了最小生成树，通过两种算法就能够从众多的边中选择那些尽可能小的边得到一个权重最小的树，这一块我们将继续讨论最小开销相关的问题。

我们首先从最简单的单源最短路径进行讨论，所谓单源最短路径，就是一个顶点出发，到其他顶点的最短路径，比如下面的这张图：
示意图

迪杰斯特拉（Dijkstra）算法

要解决这种问题，我们可以采用迪杰斯特拉（Dijkstra） 算法，下面我们来看看迪杰斯特拉算法是如何让计算机来计算最短路径的，它跟普利姆算法求最小生成树有着很多相似之处，我们就从A出发，这里我们需要一个表来记录：
示意图
dist这一行记录A到其他顶点的最短路径，path这一行记录的是最短路径所邻接的顶点，我们首先还是从A开始，与A直接相邻的两个分别是B和D，其中B的距离是2，D的距离是5，那么我们就先进行一下记录：
示意图
因为都是从A过来的，所以说直接记录为A即可，接着我们继续找到当前A路径最短的一个顶点B，此时顶点B可以到达C、D、A，因为不能走回头路，不考虑A，那么目前从A到达C的最短距离就是经过B到达的，相当于A->B加上B->C的距离：
示意图
然后我们来看顶点D，此时我们发现，除了A直接到D之外，从B也可以到达D，那么我们就可以比较一下，看是从B到D更短一些，还是从A直接到D更短一些 $min(2+2,5)$ ，通过比较，我们发现从B绕过去会更短一些，只需要4即可，所以说我们将其更新一下：
示意图
接着我们继续找到下一个离A最近的顶点D，D与顶点E和J相连，直接更新即可，比如E的最短路径就是相当于是A到D的最短路径加上D到E的路径，D到J也是同理：
示意图
此时继续找到表中下一个距离A最近的顶点J，J可以到达H或者是E，按照同样的方式，我们看看是从D直接到E更短，还是从J到E更短，进行比较 $min(6+3,8)$ ，得到结果是D直接过去更短，所以说不需要更新。然后H更新为J过去的最短路径：
示意图
然后我们来看下一个距离A最近的顶点E，E连接的就比较多了，此时E最短路径是从D过来的，那么我们就不考虑D，我们来依次看看与其相连的C、F、G、H、J（注意这里比较的是从E到这些顶点，之前比较的是从这些顶点到E，不要以为是一样的了）

  • 从E到达顶点C：$min(8+4,7)$，故C继续采用原方案。

  • 从E到达顶点F：$min(8+2,15)$，此时从E到达F路径更短，更新F。

  • 从E到达顶点G：直接更新。

  • 从E到达顶点H：$min(8+6,13)$，故H继续采用原方案。

  • 从E到达顶点J：$min(8+3,6)$，故J继续采用原方案。
    同理我们走到这一步：
    示意图
    虽然此时表已经填完了，但是我们还没有把所有的顶点都遍历完，有可能还会存在更短的路径，所以说别着急，我们还得继续看。此时继续选择下一个离A最近的顶点G，它与E、F、H、I相连，由于其实从F过来的，排除掉F，我们来看看其他三个：

  • 从G到达顶点E：min(15+9,8)min(15+9,8)，显然选择原方案就行。

  • 从G到达顶点H：min(15+3,13)min(15+3,13)，依然是选择原方案更短。

  • 从G到达顶点I：min(15+4,21)min(15+4,21)，从G到达I更短，更新。

最后得到：
示意图
此时我们来看最后一个顶点I，与其连接的有G和H，因为是从G过来的，直接比较H就行了，min(19+8,13)min(19+8,13)，维持原方案就行，至此，迪杰斯特拉算法结束。最后得到的表，就是最终的A到达各个顶点的最短路径值了，并且根据path这一栏的数据，我们就可以直接推出一条路径出来。

当然，这只是解决了单源最短路径问题，现在我们将问题的难度提升一下，比如我们现在想要求得图中每一对顶点之间的最短路径，那么该如何进行计算呢？最简单的办法就是，我们可以将所有的顶点都执行一次迪杰斯特拉算法，这样我们就可以求到所有顶点之间的最短距离了。只不过这种方式并不是最好的选择，对于这种问题，我们可以选择弗洛伊德（Floyd）算法。

弗洛伊德（Floyd）算法

比如下面的有向网图（权值别出现负数了，不然要出大问题）：
示意图
我们可以很轻松地得到它的邻接矩阵：
示意图
而弗洛伊德算法则是根据最初的邻接矩阵进行推导得出的。规则如下：

  • 从1开始，一直到n（n就是顶点数）的一个矩阵序列A1、A2、…An，我们需要从最初的邻接矩阵开始，从A1开始不断往后推。
  • 每一轮，我们都会去更新那些非对角线（对角线都是0，更新了还是0，所以说没必要看）、i行i列以外的元素，判断水平和垂直方向投影的两个元素之和是否比原值小，如果是，那就更新为新的值。迭代公式为：

    $$ A_k(i,j) = \min\big(A_{k-1}(i,j),\ A_{k-1}(i,k) + A_{k-1}(k,j)\big) $$

  • 经历n轮后，最后得到的就是最终的最短距离了。

我们从第一轮开始，第一轮是基于原有的邻接矩阵来进行处理的：
示意图
此时我们看到，除了对角线以外，就是B->C和C->B的这两个位置，我们按照上面的规则，进行计算：
示意图
同样的，我们继续看到C->B这个为止，按照同样的方式进行更新：
示意图
最后更新完成得到的结果如下：
示意图
实际上我们发现，我们计算的和相当于是绕路的结果与当前直接走的结果相比较得到的。按照的同样的方式，我们开始以下几轮：
示意图
最后我们能得到:
示意图
最后我们得到的矩阵，存放的就是所有顶点之间的最短距离了，当然这里我们只计算了最短距离，没有去记录从哪个方向到达此顶点的。

案例

实际上这个算法对我们来说是更好理解的一种算法，并且在编写程序时也会很简单，我们以下图为例：
示意图
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#define INF 210000000
#define N 4

int min(int a, int b){
    return a > b ? b : a;
}

void floyd(int matrix[N][N], int n){
    for (int k = 0; k < n; ++k)    //一共需要执行K轮
        for (int i = 0; i < n; ++i)   //i和j从0开始就行了，直接全看，不会影响结果的
            for (int j = 0; j < n; ++j)
                matrix[i][j] = min(matrix[i][k] + matrix[k][j], matrix[i][j]);   //按照规则更新就行了
}

int main(){
    int matrix[N][N] = {{0, 1, INF, INF},
                        {4, 0, INF, 5},
                        {INF, 2, 0, INF},
                        {3, INF, 7, 0}};

    floyd(matrix, N);

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j)
            printf("%d ", matrix[i][j]);
        putchar('\n');
    }
}

最后得到的结果为：
示意图
经过对比，确实是最短的路径了。

说些什么吧！

twikoo