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

相关文章

来自专栏有趣的Python

11-玩转数据结构-并查集

前面我们接触的树结构都是由父亲指向孩子,但是我们的并查集却是由孩子指向父亲。这种奇怪的树结构可以非常高效的回答一类问题: 连接问题 Connectivity P...

1492
来自专栏王小雷

Python之数据规整化:清理、转换、合并、重塑

Python之数据规整化:清理、转换、合并、重塑 1. 合并数据集 pandas.merge可根据一个或者多个不同DataFrame中的行连接起来。 panda...

2386
来自专栏逸鹏说道

小白眼中的AI之~Numpy基础

引入一下 Numpy模块, Numpy的数组使用可以查看一下帮助文档, Numpy的 array数组类型必须是一致的(后面会讲)

1034
来自专栏owent

HDU HDOJ 3398 String 解题报告

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3398

723
来自专栏nummy

Uninformed search Python实现【译】

图的搜索可以分为uninformed搜索和informed搜索,两者的区别是前者是的搜索是盲目的,它不知道目标节点在哪,而后者是启发式的搜索。

942
来自专栏Redis源码学习系列

Redis源码学习之跳表

跳跃链表简称为跳表(SkipList),它维护了一个多层级的链表,且第i+1层链表中的节点是第i层链表中的节点的子集。跳表作为一种平衡数据结构,经常和平衡树进行...

2.1K1
来自专栏吴伟祥

认识XPath(确定XML文档中某部分位置的语言)

XPath即为XML路径语言(XML Path Language),它是一种用来确定XML文档中某部分位置的语言。

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

BZOJ5027: 数学题

Description 给出a,b,c,x1,x2,y1,y2,求满足ax+by+c=0,且x∈[x1,x2],y∈[y1,y2]的整数解有多少对? Inpu...

29410
来自专栏逆向技术

逆向课程第五讲逆向中的优化方式,除法原理,以及除法优化下

        逆向课程第五讲逆向中的优化方式,除法原理,以及除法优化下 一丶除法的优化 1.有符号被除数 / 无符号除数的情况下 高级代码为: ? 汇编中优化...

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

1265. [NOIP2012] 同余方程

1265. [NOIP2012] 同余方程 ★☆   输入文件:mod.in   输出文件:mod.out 简单对比 时间限制:1 s   内存限制:128 M...

3376

扫码关注云+社区