在学习了图的根本构造和遍历形式后，咱们再持续地深刻学习一些图的根本利用。在之前的数据结构中，咱们并没接触太多的利用场景，然而图的这两类利用确是面试或考试中经常出现的问题，而且呈现的频率还十分高，不得不来好好说一说。

什么是最小生成树？

从后面的学习中，咱们应该可能发现，图就是一种扩大的树结构。对于树来说，它只有一个下级结点，同级结点之间没有关联。而图则突破了树的这些规定。咱们再反过来想想，能不能给定一个条件，那就是连贯上所有的结点，然而每个结点之间只保留一条边。这样造成的一颗简略的树其实就是可能串联所有结点的一条门路，而最小生成树的概念，其实就是对于有权图来说，权数起码的那条可能串连起所有结点的边的门路，或者也能够说是最小连通树、最小连通子图、最小代价树。

从上图中就能够看出，对于一个有权图来，能够有许多生成树的形式，不过不同的路线形式的后果会不同，只有最初一个门路造成的生成树具备门路最小的那颗树，就是咱们须要的最小生成树。

为什么要强调是有权图呢？因为如果是无权图，所有结点连接起来的计划其实就没有什么太大的意义了，因为不论从哪个结点登程走哪条门路可能权值都是一样的。而带权门路则总会有一条最佳的门路是能够将所有结点遍历实现并且权数还是最小的。最典型的利用就是地图上哪条线路老本起码呀，办公楼布线怎么走线最经济之类相干的题目，根本都会牵涉到最小生成树的概念。

对于最小生成树的最经典的算法，Prim 和 Kruskal 这两个大神级别的算法是绕不过来的槛，上面咱们就来浅显地学习一下。

第一种算法 Prim

Prim 算法，中文名 普里姆 算法。起源就不多说了，反正是集体名，这篇文章和下篇文章中图的利用的这些算法名称都是人名相干的。他们发现并最后应用了这些算法，而后就将这些算法以他们的名字命名了。

Prim 算法的核心思想就是：从一个结点登程，查看这个结点的所有的边中权值最小的那条边，而后加上这条边所连贯的那个结点的所有边，再一起看哪个边的权值最小，而后始终反复这些步骤，反正就是所有结点到咱们登程的这个结点中所有权值最小的边都看一遍，并且让它们可能连贯所有结点就实现了。

看图是不是就清晰多了。咱们一步一步地看。

  • 1) 首先咱们从第 1 个结点登程，而后看第 1 个结点相干的边哪个权值最小，很显著，咱们要选抉择 <1, 2> 这条边，而后将结点 2 退出到抉择中
  • 2）在结点 1 和结点 2 中抉择最权值最小的边并连贯到新的结点，在这里咱们抉择的是 <1, 3> 这条边，于是结点 3 也退出到抉择中
  • 4）在结点 1、2、3 的所有边中，选择权值最小的边，能够看到 <2, 3> 这条边的权值最小，然而 2 和 3 都曾经连通了，所以抉择下一个最小的边 <3, 4> ，结点 4 还没有退出到曾经连通的结点中，于是就走 <3, 4> 这条边，结点 4 退出已连通结点中
  • 5）同样地，在结点 1、2、3、4 中选择权值最小的边，这时只有 <4, 6> 边是最小的，并且结点 6 也没有退出到已连通结点中，抉择这条路线，结点 6 退出连通结点中
  • 6）最初，在结点 1、2、3、4、6 中查找权值最小的边，失去 <6, 5> 这条边，结点 5 也没连通，于是抉择这条门路，退出结点 5
  • 7）所有结点都曾经连通，权值累加结点为 19 ，以后的这条门路就是最小权值门路，所造成的这一条门路就是一颗最小生成树了

从这个步骤和图释来说，大家能够本人尝试写写这个 Prim 算法的代码，其实并不简单。咱们须要一个汇合来搁置曾经连通的结点信息，当查找门路的时候找到的最小权值门路连通的结点不在汇合中，就退出到汇合中。而后一直累加所有的门路权值，最初就失去了遍历整张图的最小生成树门路。

// 普里姆算法function Prim($graphArr){    $n = count($graphArr);    // 记录 1 号顶点到各个顶点的初始间隔    $dis = [];    for ($i = 1; $i <= $n; $i++) {        $dis[$i] = $graphArr[1][$i];    }    // 将 1 号顶点退出生成树    $book[1] = 1; // 标记一个顶点是否曾经退出到生成树    $count = 1; // 记录生成树中的顶点的个数    $sum = 0; // 存储门路之和    // 循环条件 生成树中的顶点的个数 小于 总结点数    while ($count < $n) {        $min = INFINITY;        for ($i = 1; $i <= $n; $i++) {            // 如果以后顶点没有退出到生成树，并且记录中的权重比以后权重小            if (!$book[$i] && $dis[$i] < $min) {                // 将 $min 定义为以后权重的值                $min = $dis[$i];                $j = $i; // 用于筹备将顶点退出到生成树记录中            }        }        $book[$j] = 1; // 确认将最小权重退出到生成树记录中        $count++; // 顶点个数减少        $sum += $dis[$j]; // 累加门路和        // 调整以后顶点 $j 的所有边，再以 $j 为两头点，更新生成树到每一个非树顶点的间隔        for ($k = 1; $k <= $n; $k++) {            // 如果以后顶点没有退出到生成树，并且记录中的 $k 权重顶点大于 $j 顶点到 $k 顶点的权重            if (!$book[$k] && $dis[$k] > $graphArr[$j][$k]) {                // 将记录中的 $k 顶点的权重值改为 $j 顶点到 $k 顶点的值                $dis[$k] = $graphArr[$j][$k];            }        }    }    return $sum;}$graphArr = [];BuildGraph($graphArr); // 之前文章中的生成邻接矩阵的函数echo Prim($graphArr); // 19

咱们运行代码并输出测试数据。

php 5.4图的利用：最小生成树.php请输出结点数：6请输出边数：9请输出边，格局为 出 入 权：2 4 11请输出边，格局为 出 入 权：3 5 13请输出边，格局为 出 入 权：4 6 3请输出边，格局为 出 入 权：5 6 4请输出边，格局为 出 入 权：2 3 6请输出边，格局为 出 入 权：4 5 7请输出边，格局为 出 入 权：1 2 1请输出边，格局为 出 入 权：3 4 9请输出边，格局为 出 入 权：1 3 219

能够看到输入的后果和咱们预期的一样。代码中曾经有很具体的正文阐明了，如果间接看代码比拟晕的话，大家能够拿调试工具进行断点的单步调试来看一下具体的运行状况。在这里咱们先看一下那个 dis[] 中最初都保留了什么货色。

Array(    [1] => 9999999    [2] => 1    [3] => 2    [4] => 9    [5] => 4    [6] => 3)

INFINITY 是咱们定义的一个常量，在初始化 graphArr 这个邻接矩阵时，将所有的边都设置为 INFINITY 了，次要就是不便咱们前面进行最小值的比对。这个 INFINITY 咱们设置的是 9999999 这样一个十分大的数。dis[] 中其实蕴含的就是结点 1 所通过的每条边所抉择的权值，把他们加起来就是咱们的最终门路长度。

第二种算法 Kruskal

Prim 算法好玩吗？置信通过具体的算法你对最小生成树的概念就更清晰了，不晓得你会不会有个这样的想法：间接遍历所有的边，给他们按权值排序，这样咱们再顺次遍历这个排序后的边构造数组，而后将边的结点退出到最终要生成的树中，这样不也能造成一个最小生成树嘛！哇塞，你要是真的想到这个计划了那要给一个大大地赞了。这种形式就是咱们最小生成树的另一种明星算法：Kruskal 算法。它的中文名字能够叫做 克鲁斯卡尔 算法。

看这个步骤是不是和 Prim 就齐全不一样了？不急，咱们还是一步一步地来看。

  • 1）在所有的边中，抉择最小的那条边，也就是 <1, 2> 这条边，结点 1 和结点 2 连通
  • 2）接着抉择第二小的边，<1, 3> 边符合条件，并且结点 3 没有连通，退出结点 3
  • 3）持续抉择最小的边，此时最小的边是 <4, 6> ，这两个结点都没有连通，间接退出
  • 5）接下来是 <6, 5> 这条边最小，持续连通并将结点 5 退出
  • 6）好了，左右两边成型了，当初最小的边是 <2, 3> 边，不过结点 2 和结点 3 曾经连通了，放弃！抉择 <4, 5> 边，同样，结点4 和结点 5 也曾经连通了，放弃！抉择 <3, 4> 边，OK，这两条边还没有连通，间接连通，所有结点连通结束，最小生成树实现！

不错吧，又学会一个新的套路，大家也能够试试依照下面的步骤和图释来本人先写写代码。须要留神的咱们要先给所有的边排序，能力进行这个算法的操作。另外，每次判断结点连通也是一件麻烦的工作，应用深度优先或者广度优先遍历是没问题的，但效率太低，让咱们看看大神（算法书中）们是怎么做的。

// 克鲁斯卡尔算法function Kruskal($graphArr){    global $map, $f;    $hasMap = [];    $i = 1;    // 转换为序列模式不便排序    // O(mn)或O(n^2)，能够间接建图的时候应用单向图进行建设就不须要这一步了    foreach ($graphArr as $x => $v) {        foreach ($v as $y => $vv) {            if ($vv == INFINITY) {                continue;            }            if (!isset($hasMap[$x][$y]) && !isset($hasMap[$y][$x])) {                $map[$i] = [                    'x' => $x,                    'y' => $y,                    'w' => $vv,                ];                $hasMap[$x][$y] = 1;                $hasMap[$y][$x] = 1;                $i++;            }        }    }    // 应用快排依照权重排序    quicksort(1, count($map));    // 初始化并查集    for ($i = 1; $i <= count($graphArr); $i++) {        $f[$i] = $i;    }    $count = 0; // 已记录结点数量    $sum = 0; // 存储门路之和    for ($i = 1; $i <= count($map); $i++) {        // 判断一条边的两个顶点是否曾经连通，即判断是否已在同一个汇合中        if (merge($map[$i]['x'], $map[$i]['y'])) { // 如果目前已连通，则选用这条边            $count++;            $sum += $map[$i]['w'];        }        if ($count == count($map) - 1) { // 直到选了n-1条边后退出            break;        }    }    return $sum;}

Oh my God！代码多了好多，还有好多莫名其妙的货色呈现了。在上文中说过，咱们要应用 Kruskal 算法就得先给边排序。所以咱们先将邻接矩阵转换成 map[x,y,w] 的模式，x 和 y 仍然是代码两个结点，而 w 代表权重。这样的一个能够看成是边对象的数组就比拟不便咱们进行排序了。

接着咱们应用疾速排序依照权值进行排序，具体的快排算法咱们在前面学习排序的时候再具体阐明，大家能够间接在文章底部复制测试代码链接查看残缺的代码。

接下来就是应用并查集进行 Kruskal 算法的操作了。并查集就是代替深度和广度优先遍从来疾速确定结点连通状况的一套算法。

$f = [];// 并查集寻找先人的函数function getf($v){    global $f;    if ($f[$v] == $v) {        return $v;    } else {        // 门路压缩        $f[$v] = getf($f[$v]);        return $f[$v];    }}// 并查汇合并两子集合的函数function merge($v, $u){    global $f;    $t1 = getf($v);    $t2 = getf($u);    // 判断两个点是否在同一个汇合中    if ($t1 != $t2) {        $f[$t2] = $t1;        return true;    }    return false;}

它自身还是通过递归的形式来将结点保留在一个数组中，通过判断两个点是否在同一个汇合中，即两个结点是否有独特的先人来确定结点是否曾经退出并且连通。

对于并查集的常识自己把握的也并不是很深刻，所以这里就不班门弄斧了，大家能够本人查阅相干的材料或者深入研究各类算法书籍中的解释。

最初运行代码输入的后果和 Prim 算法的后果是统一的，都是 19 。

总结

怎么样？最小生成树是不是很好玩的货色，图的构造其实是很简单的，不过越是简单的货色可能玩出的花活也越多。然而反过来说，很多公司的面试过程中对于图的算法能考到这里的也都是大厂了，个别的小公司其实能简略地说一说深度和广度就曾经不错了。咱们的学习还要持续，下一篇咱们将学习的是另一个图的广泛应用：最短距离。

明天的测试代码均依据 《啊哈！算法》 改写为 PHP 模式，参考资料仍然是其它各类教材。

测试代码：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/5.图/source/5.4图的利用：最小生成树.php

参考文档：

《数据结构》第二版，严蔚敏

《数据结构》第二版，陈越

《数据结构高分笔记》2020版，天勤考研

《啊哈！算法》

===========

各自媒体平台均可搜寻【硬核项目经理】