学习完图的基本结构和遍历方法，接下来我们继续学习图的一些基本应用。在前面的数据结构中，我们并没有接触太多的应用场景，但是图中的两类应用确实是面试或者考试中经常遇到的问题，出现的频率还是很高的，所以不得不说一下他们。什么是最小生成树？从前面的学习中，我们应该可以发现图是一种扩展的树结构。对于一棵树，它只有一个上级节点，兄弟节点之间没有关系。图打破了这些树的规则。我们反过来想一下，能不能给个条件，就是把所有的节点都连接起来，但是每个节点之间只保留一条边。这样形成的一棵简单的树其实就是一条可以连接所有节点的路径，而最小生成树的概念对于一个带权图来说，其实就是可以连接所有节点的权重最小的边。的路径，或者也可以说是最小连通树，最小连通子图，最小代价树。从上图可以看出，对于一个带权图，可以有多种生成树的方式，但是不同的路由方式结果会有所不同。只有最后一条路径形成的生成树才有路径最小的树。这是我们需要的最小生成树。为什么强调是地图权呢？因为如果是无权图的话，连接所有节点的方案其实意义不大，因为无论从哪个节点开始，走哪条路，权值都可能是一样的。加权路径总有一条能遍历所有节点且权值最小的最优路径。最典型的应用是地图上哪条线路成本最低，写字楼布线如何布线最经济等相关话题，基本都涉及到最小生成树的概念。关于最小生成树最经典的算法，Prim和Kruskal这两个神级算法，绕不过门槛。让我们简单了解一下。第一种算法是PrimPrim算法，中文名Prim算法。产地我就不多说了。无论如何，这是一个个人名字。这篇文章和下一篇文章用到的算法名称，都与人名有关。他们发现并最初使用了这些算法，然后以他们的名字命名。Prim的算法核心思想是：从一个节点开始，看这个节点的所有边中权值最小的边，然后把这条边连接的节点的所有边相加，再看哪个edge边的权重最小，然后一直重复这些步骤。反正就是看从所有节点到我们开始的那个节点的ownership值最小的边，让他们能够连接所有的节点。看图就清楚多了。让我们一步步来看。1）首先，我们从第一个节点开始，然后看哪边的权值最小。显然，我们需要选择边<1,2>，然后将节点2添加到Selection2）从节点1和节点2中选择权重最小的边连接到新节点。这里我们选择了边<1,3>，所以节点3也加入了Selecting4)在节点1,2,3的所有边中，选择权重最小的边。可以看到边<2,3>的权重最小，但是2和3已经连通了，所以选择下一条最小的边<3,4>，节点4还没有加入到连通的节点中，所以去边<3,4>,节点4加入到连接的节点中5)相同因此，在节点1,2,3,4中选择权重最小的边。此时只有边<4,6>最小，节点6不加入连接节点。选择这条Route，将节点6添加到相连的节点中6)最后，在节点1、2、3、4、6中找到权重最小的边，得到边<6,5>，节点5不是connected，所以选择这条路径，添加节点57）所有节点都连通，权重累加节点为19，当前路径为最小权重路径，形成的路径为最小生成树从这一步和图解，可以试试自己写这个Prim算法的代码，并不复杂。我们需要一个集合来存储连接的节点信息。在搜索路径时，找到的权重值最小的路径所连接的节点不在集合中，因此将其加入集合中。然后不断累加所有的路径权值，最后得到遍历整个图的最小生成树路径。//Prim的算法函数Prim($graphArr){$n=count($graphArr);//记录顶点1到每个顶点的初始距离$dis=[];对于($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(!$书[$k]&&$dis[$k]>$graphArr[$j][$k]){//将记录中$k个顶点的权重值改为$j个顶点到$k个顶点的值$dis[$k]=$graphArr[$j][$k];}}}返回$sum;}$graphArr=[];BuildGraph($graphArr);//上一篇文章中用来生成邻接矩阵的函数echoPrim($graphArr)；//19我们运行代码，输入测试数据php5.4图的应用：minimumspanningtree.php请输入节点数：6请输入边数：9请输入边的访问权限格式：2411请输入边，格式为访问权限：3513请输入边，格式为访问权限：463请输入边，格式为访问权限：564请输入边，格式为访问权：236请输入边，格式为访问权：457请输入边，格式为访问权：121，请输入边，格式为访问权:349请在旁边输入，格式为访问权限：13219，可以看到输出结果和我们预期的一样。代码中已经有很详细的注释了。如果直接看代码觉得头晕，可以使用调试工具进行断点单步调试，看看具体的运行情况。这里我们先看看最后那个dis[]里面保存的是什么。Array([1]=>9999999[2]=>1[3]=>2[4]=>9[5]=>4[6]=>3)INFINITY是我们定义的一个常量，在初始化graphArr的时候这个邻接矩阵，所有的边都设置为INFINITY，主要是为了方便后面比较最小值。我们把这个INFINITY设置成一个非常大的数，比如9999999。dis[]其实包含的是节点1经过的每条边选择的权值，它们相加就是我们最终的路径长度。第二种算法KruskalPrim算法好玩吗？相信通过具体的算法，你对最小生成树的概念会更加清晰。不知道大家有没有这样的想法：直接遍历所有的边，按权重排序，这样我们就可以依次遍历这个排序的边结构数组，然后把边节点加入到最终要生成的树中，所以也可以形成最小生成树！哇，如果你真的想到了这个方案，你应该给它一个大大的赞。这种方法是我们最小生成树的另一种明星算法：Kruskal算法。它的中文名字可以叫做Kruskal算法。看看这一步是不是和Prim完全不一样？别着急，我们一步步来看。1）在所有的边中，选择最小的边，即边<1,2>，节点1和节点2相连2）然后选择次小的边，边<1,3>如果条件是遇到了，和节点3不相连，加入节点33)继续选择最小边，此时最小边是<4,6>，这两个节点不相连，直接加5)接下来是<6,5>是最小的边，继续连接加上节点5到6）好了，左右边就形成了，现在最小的边是<2,3>边，但是节点2和节点3已经连起来了，给向上！选择<4,5>边，同理，节点4和节点5已经连通，放弃！选择<3,4>边，OK，这两条边还没连起来，直接连起来，所有节点都连起来，最小生成树就完成了！不错，我学会了一个新套路。大家也可以按照上面的步骤和图解自己尝试写代码。需要注意的是，在执行这个算法的操作之前，我们必须先对所有的边进行排序。另外，每次判断节点的连通性也是一个耗时的工作。用深度优先或者广度优先遍历都没有问题，但是效率太低了。且看高手们（算法书）是怎么做的。//Kruskal算法函数Kruskal($graphArr){global$map,$f;$hasMap=[];$i=1;//转为序列方便排序//O(mn)orO(n^2)，可以直接用单向图建图，所以不需要foreach这一步($graphArras$)x=>$v){foreach($vas$y=>$vv){if($vv==INFINITY){继续；}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));//初始化并搜索($i=1;$i<=count($graphArr);$i++){$f[$i]=$i;}$计数=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){//退出break直到选择了n-1条边；}}return$sum;}天哪！代码多了很多，出现了很多莫名其妙的东西。上面说了，如果我们要使用Kruskal算法，就得先对边进行排序。所以我们先将邻接矩阵转化为map[x,y,w]的形式，x和y仍然是代码的两个节点，w代表权重。这样一个可以看作边??缘对象的数组，更方便我们进行排序。然后我们使用快速排序，按照权重排序。具体的快速排序算法在后面学习排序的时候会详细讲解。可以直接复制文章底部的测试代码链接查看完整代码。下一步是使用联合搜索来执行Kruskal算法的操作。联合搜索是一组算法，用来快速判断节点的连通性，而不是深度和广度优先遍历。$f=[];//寻找祖先函数functiongetf($v){global$f;如果($f[$v]==$v){返回$v;}else{//路径压缩$f[$v]=getf($f[$v]);返回$f[$v]；}}//合并函数merge($v,$u){global$f;$t1=getf($v);$t2=getf($u);//判断两个点是否在同一个集合中if($t1!=$t2){$f[$t2]=$t1;返回真；}returnfalse;}还是递归的把节点保存在一个数组中，通过判断两个点是否在同一个集合中，即两个节点是否有共同的祖先来判断节点是否已经加入并连接。关于merge和search的知识我了解不深，这里就不大惊小怪了。可以自行查阅相关资料，也可以深入研究各种算法书籍中的讲解。最后运行代码的结果和Prim的算法结果一致，都是19。总结一下呢？最小生成树是不是一个很有趣的东西？图的结构其实很复杂，但是越复杂的东西，能玩的花样就越多。但另一方面，在很多公司的面试过程中，能考到这里图的算法的，都是大公司。其实一般的小公司可以简单的谈深度和广度。我们的研究还会继续，下一篇我们要研究的是图的另一个广泛应用：最短距离。今天的测试代码都是按照《啊哈！算法》改写成PHP形式的，参考资料还是其他各种教材。测试代码：https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/5。图/source/5.4图的应用：MinimumSpanningTree.php参考文档：《数据结构》第二版，闫伟民《数据结构》第二版，陈越《数据结构高分笔记》2020年版，天琴考研《啊哈！算法》==============================================================================================================================================各媒体平台均可搜索【硬核项目经理]
