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 条评论
登录 后参与评论

相关文章

来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》第12章 pandas高级应用12.1 分类数据12.2 GroupBy高级应用12.3 链式编程技术12.4 总结

前面的章节关注于不同类型的数据规整流程和NumPy、pandas与其它库的特点。随着时间的发展,pandas发展出了更多适合高级用户的功能。本章就要深入学习pa...

4997
来自专栏海天一树

小朋友学数据结构(16):基于邻接矩阵的的深度优先遍历和广度优先遍历

这两个图其实是一样的,只是画法不同罢了。第一张图更有立体感,第二张图更有层次感,并且把A点置为顶点(事实上图的任何一点都可以做为顶点)。

895
来自专栏小白客

每天学习一点儿算法--快速排序

快速排序是一种常用的优雅的排序算法,它使用分而治之的策略。 那么分而治之(D&C)是一种怎样的策略呢? 分而治之 分而治之(D&C)的要点只有两个: 找出简单...

2724
来自专栏ATYUN订阅号

帮助数据科学家理解数据的23个pandas常用代码

返回给定轴缺失的标签对象,并在那里删除所有缺失数据(’any’:如果存在任何NA值,则删除该行或列。)。

624
来自专栏WD学习记录

Python数据结构与算法笔记(3)

递归是一种解决问题的方法,将问题分解为更小的子问题,直到得到一个足够小的问题可以被很简单地解决,通常递归设计函数调用自身。递归允许我们编写优雅的解决方案,解决可...

851
来自专栏生信技能树

R语言中的排序,集合运算,reshape,以及merge总结

不想排版,心情也不好,但是这个知识点很重要,尤其是学习R语言的朋友,请仔细看~ 一直以来我都是随便看了点R的编程教程,因为我学了一点点C,所以还算有基础,现在基...

26911
来自专栏机器学习和数学

[Tensorflow] TensorFlow之Hello World!(2)

TensorFlow入门的第一篇和大家聊了?graph图,op操作,node节点。对TensorFlow有了一个简单的认识,今天主要和大家分享的是TensorF...

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

P3379 【模板】最近公共祖先(LCA)

题目描述 如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。 输入输出格式 输入格式: 第一行包含三个正整数N、M、S,分别表示树的结点个数...

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

#103. 子串查找

内存限制:256 MiB时间限制:500 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: 匿名 提交提交记录统计讨论测试数据 题目描述 这是一道模...

2647
来自专栏python读书笔记

《python算法教程》Day4 - 拓扑排序(基于有向无环图)拓扑排序简介代码实例

这是《python算法教程》的第4篇读书笔记。这篇笔记的主要内容为拓扑排序。 拓扑排序简介 在将一件事情分解为若干个小事情时,会发现小事情之间有完成的先后次序之...

34411

扫码关注云+社区