首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

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

作者头像
用户1327360
发布2018-03-07 10:44:21
1.2K0
发布2018-03-07 10:44:21
举报
文章被收录于专栏:决胜机器学习决胜机器学习

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数据结构(一)——顺序结构线性表

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2017-07-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 决胜机器学习 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 相关阅读:
    • PHP数据结构(十一) ——图的连通性问题与最小生成树算法(1)
      • PHP数据结构(十) ——有向无环图与拓扑算法
        • PHP数据结构(九) ——图的定义、存储与两种方式遍历
          • PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践2)
            • PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践1)
              • PHP数据结构(八) ——赫夫曼树实现字符串编解码(理论)
                • PHP数据结构(七) ——串与实现KMP算法
                  • PHP数据结构(六) ——树与二叉树之概念及存储结构
                    • PHP数据结构(六) ——数组的相乘、广义表
                      • PHP数据结构(五) ——数组的压缩与转置
                        • PHP数据结构(四) ——队列
                          • PHP数据结构(三)——运用栈实现括号匹配
                            • PHP数据结构(二)——链式结构线性表
                              • PHP数据结构(一)——顺序结构线性表
                              领券
                              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档