PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

PHP数据结构(十一)——图的连通性问题与最小生成树算法(2)

(原创内容,转载请注明来源,谢谢)

再次遇到微信公众号限制字数3000字的问题。因此将Kruskal算法放于本文中进行描述。本文接上一篇文章。

4、Kruskal算法

1)该算法的时间复杂度为O(eloge),e表示边的数目,即该算法的时间复杂度和顶点数目无关。该算法适用于边数较少的稀疏网。

2)算法内容

假设N={V, {E}}是连通网,算法初始状态为包含图中的所有的点,没有边的T=(V, {})开始,图中的每一个顶点自成一个连通分量,重复执行以下操作:

在E中选一条代价最小的边,如果此边符合该边依附在两个不同的连通分量上的要求,则将此边加入T,否则找代价第二小的边。以此类推,直至T中所有顶点都落在同一个连通分量上位置。则TE包含n-1条边,T=(V, {TE})是最小生成树。

该算法需要引入一个二维数组,记录任意两个顶点之间的权值,如果两个顶点没有连接,则权值为无穷大。

5、总结

Prim算法和Kruskal算法,区别在于从顶点切入还是从边切入。因此,当顶点较多但边相对较少时,可以使用Kruskal算法;反之,顶点较少而边相对较多时,可以使用Prim算法。两个算法都需要引入一个二维数组,用于存储任意两点间的权值,当两点没有连接时,权值为无穷大,表示该点无法直接到达另一点。

6、编码实现

PHP实现Prim算法和Kruskal算法的运行结果如下:

    //Kruskal算法:以边为依据生成最小生成树
         publicfunction getKruskalResult(){
                   //进行数组转换,将siteWeigh转成一维数组'ij'=>weigh的形式
                   $arrKruskal= $this->changeArray($this->siteWeigh);
                   //对转换后的数组进行排序,由从小到大的序列进行排序,便于后面取权值小的边
                   $arrKruskal= $this->sortArray($arrKruskal);
                   /*Array( [0] => Array ( [line] => 41 [weigh] => 5 ) [1] => Array ( [line]=> 10 [weigh] => 10 ) [2] => Array ( [line] => 31 [weigh] => 10)
                   [3]=> Array ( [line] => 43 [weigh] => 10 ) [4] => Array ( [line] =>20 [weigh] => 15 )
                   [5]=> Array ( [line] => 40 [weigh] => 20 ) [6] => Array ( [line] =>32 [weigh] => 25 ) )*/
                   $nodeNum= count($arrKruskal);//获取节点数目
                   $resStack= array();//用于存放结果路径,格式0=>ij,1=>jk
                   $nodeStack= array();//判断新取的边是否在同一个连通分量
                   //遍历生成的数组,因为已经排好序,所以从第一个开始遍历
                   //如果遍历到的边,两个节点都已经纳入结果集,说明该边是冗余的边
                   //则该边不是最小生成树,跳过,遍历下一条
                   foreach($arrKruskalas $line){
                            $node1= $line['line'][0];//获取两个阶段的编号
                            $node2= $line['line'][1];
                            if(in_array($node1,$nodeStack) && in_array($node2, $nodeStack)){
                                     continue;//判断两个节点都在结果集就跳过
                            }
                            array_push($resStack,$line);//边进结果集
                            if(!in_array($node1,$nodeStack)){
                                     array_push($nodeStack,$node1);//边的节点进结果集
                            }
                            if(!in_array($node2,$nodeStack)){
                                     array_push($nodeStack,$node2);
                            }                          
                   }       
                   //计算权值
                   $sum= 0;
                   foreach($resStackas $nodeNum => $node){
                            $sum+= $node['weigh'];
                   }
                   returnarray('resRoad' => $resStack, 'resSum' => $sum);
         }
        //提供给kruskal算法的数组转换,将二维数组转换成一维数组
         privatefunction changeArray($arrToChange){
                   $res= array();
                   $nodeNum= count($arrToChange);
                   for($i=0;$i<$nodeNum;$i++){
                            //因为数组是三角对称的,只需要遍历半边即可
                            //并且i==j即单个顶点的情况不需要遍历
                            for($j=0;$j<$i;$j++){
                                     if(999== $arrToChange[$i][$j]){
                                               continue;//不存在的线不需要遍历
                                     }
                                     //$i.$j表示边ij
                                     $res[]= array('line' => $i.$j, 'weigh' => $arrToChange[$i][$j]);
                            }
                   }
                   return$res;
         }
    //提供给kruskal算法的数组排序,采用快速排序的思想
         privatefunction sortArray($arrToSort){
                   $res= array();
                   $nodeNum= count($arrToSort);//获取节点总数
                   $firstNode= array_shift($arrToSort);//取第一个节点,用于快速排序 
                   $leftSmallArr= array();//存放比第一个节点小的
                   $rightBigArr= array();//存放比第一个节点大的
                   foreach($arrToSortas $node){
                            if($node['weigh']< $firstNode['weigh']){
                                     array_push($leftSmallArr,$node);//小于第一个节点的分到左边数组,否则去右边数组
                            }else{
                                     array_push($rightBigArr,$node);
                            }
                   }
                   $leftRes= array();
                   if(count($leftSmallArr)> 1){
                            $leftRes= $this->sortArray($leftSmallArr);//当数组多个元素,调用函数再次排序
                   }elseif(1 == count($leftSmallArr)){
                            $leftRes= $leftSmallArr;//当数组只有一个元素,则返回此元素
                   }else{
                   }
                   //同leftRes
                   $rightRes= array();
                   if(count($rightBigArr)>= 1){
                            $rightRes= $this->sortArray($rightBigArr);
                   }elseif(1 == count($rightBigArr)){
                            $rightRes= $rightBigArr;
                   }else{
                   }                          
                   returnarray_merge($leftRes, array($firstNode), $rightRes);
         }
$minTree = new MinTree();
$kruskalRes = $minTree->getKruskalResult();
echo '采用kruskal算法,获取的最小生成树为:';
print_r($kruskalRes['resRoad']);
echo '<br />最终的权值和为:'.$primRes['resSum'].'<br/>';

题外话:两种最小生成树算法,Prim以节点为切入点获取最小生成树,Kruskal以边为切入点获取最小生成树。两者实现方式较为不同,Prim算法主要以栈的思想进行解决,因此实际编码过程中进出栈的处理逻辑需要理清楚;Kruskal重在排序,当每条边的长度排好时,其他问题迎刃而解。

——written by linhxx 2017.07.09

相关阅读:

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(1)

PHP数据结构(十) ——有向无环图与拓扑算法

PHP数据结构(九) ——图的定义、存储与两种方式遍历

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践2)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践1)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(理论)

PHP数据结构(七) ——串与实现KMP算法

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六) ——数组的相乘、广义表

PHP数据结构(五) ——数组的压缩与转置

PHP数据结构(四) ——队列

PHP数据结构(三)——运用栈实现括号匹配

PHP数据结构(二)——链式结构线性表

PHP数据结构(一)——顺序结构线性表

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-07-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏mathor

搜索(2)

1154
来自专栏哈雷彗星撞地球

算法之路(二)呈现O(logN)型的三个算法典型时间复杂度

我们知道算法的执行效率,可以从它的时间复杂度来推算出一二。而典型的时间复杂度有哪些类型呢?

634
来自专栏云端架构

【云端架构】教你口算MD5算法

对MD5算法简要的叙述可以为:MD5以512位分组来处理输入的信息,且每一分组又被划分为16个32位子分组,经过了一系列的处理后,算法的输出由四个32位分组组成...

45214
来自专栏互联网大杂烩

快速排序

快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值...

502
来自专栏数据结构与算法

洛谷P3273 [SCOI2011]棘手的操作

题目描述 有N个节点,标号从1到N,这N个节点一开始相互不连通。第i个节点的初始权值为a[i],接下来有如下一些操作:U x y: 加一条边,连接第x个节点和第...

3137
来自专栏xcywt

《大话数据结构》一些基础知识

第一章 数据结构绪论 1.4 基本概念和术语 1.4.1 数据 数据:描述客观事物的符号,是计算机中可以操作的对象,是能被极端及识别,并输入给计算机处理的符号集...

3329
来自专栏小樱的经验随笔

qsc oj 22 哗啦啦村的刁难(3)(随机数,神题)

哗啦啦村的刁难(3) 发布时间: 2017年2月28日 20:00   最后更新: 2017年2月28日 20:01   时间限制: 1000ms   内存限制...

2679
来自专栏恰同学骚年

数据结构基础温故-5.图(中):图的遍历算法

上一篇我们了解了图的基本概念、术语以及存储结构,还对邻接表结构进行了模拟实现。本篇我们来了解一下图的遍历,和树的遍历类似,从图的某一顶点出发访问图中其余顶点,并...

631
来自专栏Python小屋

哈夫曼编码原理与Python实现代码(附手动推导过程原稿真迹)

哈夫曼编码依据字符出现概率来构造异字头(任何一个字符的编码都不是其他字符的前缀)的平均长度最短的码字,通过构造二叉树来实现,出现频次越多的字符编码越短,出现频次...

3118
来自专栏编程理解

数据结构(一):二叉树

二叉树( binary tree )是有限节点集合构成的结构,其结构的递归定义为:

592

扫描关注云+社区