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

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

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

一、连通分量和生成树

1、无向图

设E(G)为连通图G的所有边的集合,从图的任意一点出发遍历图,可以将E(G)分为T(G)和B(G),T表示已经遍历过的边的集合,B表示剩余边的集合。因此,T与图G的所有顶点构成的极小连通子图,就是G的一棵生成树。由深度优先搜索的称为深度优先生成树;由广度优先搜索的称为广度优先生成树。

2、有向图

有向图和无向图类似。有向图的强连通分量,是对图进行深度优先遍历,遍历完成后,从被遍历的最后一个节点开始,做逆向的深度优先遍历。

二、关节点和重连通分量

1、定义

1)当删去图的节点V以及和B相关联的各边后,图若被分割成两个或以上的图,则称V为关节点。

2)一个没有关节点的连通图,称为重连通图。

3)删去k个节点后,才会破坏图的连通性,则该图的连通度为k。

2、获取方式

图的关键点数量可以用深度优先搜索的方法获取。

关节点主要有以下两个特性:

1)若生成树的根有两个以上的子节点,则此根为关节点。

2)若生成树的某个非叶子节点V,其若干棵子树以及子树的子节点均没有指向V的祖先的回边,则V即为关节点。

3)关节点至少要与两个节点相连(如果只和一个节点相连,则是叶子节点,其是否断开不影响图的连通性)。

根据以上两个特性,主要判断方式如下:

1)数据结构利用上一篇将图遍历时候的节点结构

class Node{
         public $val = null;
         public $arrNext =array();//存储下一个节点位置的数组
}

2)遍历每一个节点,对节点进行筛选,以下三种情况,V不是关节点,其余V是关节点。

A. 当节点V的arrNext数组小于或等于1时,V为叶子节点或为单独的节点,则V不是关节点;

B. 如果V的某个子节点vi,是V其他子节点vk的子节点vx(不含V)的子节点,则V不是关节点;

C.如果V的某个子节点vi的子节点vk(不含V),是V其他子节点 vx(不含vk)的子节点,则V不是关节点。

否则,节点V是关节点。

三、最小生成树

1、场景

现假设需要对一个城市的某几个区域进行通信网络的连接,每两个点之间有自己的耗费,现需要把这几个点连接起来行程通信网,又想要最节省耗费。

将每个区域看成一个节点,区域之间看成无向图的边,每两个点之间的耗费看成边的权,则该问题化简为求一个无向图考虑到权值情况下的的最小生成树。

2、概念

1)生成树的代价:各边权值的和,代价最小时称为最小生成树。

2)MST:最小生成树的性质,假设连通网N=(V, {E}),U是顶点集V的一个非空子集,若(u, v)是一条具有最小权值的边,其中u属于U,v属于V-U,则必存在一棵包含点(u, v)的最小生成树。

3)最小生成树有两种算法,一种叫做普里姆(Prim)算法,一种叫做克鲁斯卡尔(Kruskal)算法。

(PS:本来写文章时,是将Prim和Kruskal算法放在一篇的,也便于比较,但是微信公众号有个限制3000字的规定,所以我只能把Kruskal算法挪到下一篇,见谅。)

3、Prim算法

1)该算法的时间复杂度为O(n2),即其时间复杂度和边的数目无关,仅和顶点数目有关,适用于边数较多的稠密网。

2)算法内容

假设N={V, {E}}是连通网,TE是N上最小生成树的集合。算法从U={u0}(即图上任意一点),TE={}开始,重复执行以下操作:

在所有的u属于V,v属于V-U的边(u, v)属于E,着一条代价最小的边(u0,v0),并入集合TE,v0并入U,直到U=V为止。则TE包含n-1条边,T=(V, {TE})是最小生成树。

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

4、Kruskal 挪至下一篇文章描述,原因见上述 斜体字。

5、总结

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

6、编码实现

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

源码如下:

<?php
class MinTree{
         public$siteWeigh = array();
         publicfunction __construct($data = null){
                   if($data!= null){
                            $this->siteWeigh= $data;
                   }else{
                            //构造二维数组,存放任意两点间的权值
                            //由于是无向图,因此具有轴对称性
                            //用999表示两个点没有连接 
                            $this->siteWeigh= array(
                                     0=> array(999, 10, 15, 999, 20),
                                     1=> array(10, 999, 999, 10, 5),
                                     2=> array(15, 999, 999, 25, 999),
                                     3=> array(999, 10, 25, 999, 10),
                                     4=> array(20, 5, 999, 10, 999)
                            );
                   }
         }
         //Prim算法:以顶点为依据生成最小生成树
         publicfunction getPrimResult(){
                   $arrTree= $this->siteWeigh;
                   $allKeys= array_keys($arrTree);//获取全部节点
                   $nodeNum= count($allKeys);
                   $nodeStack= array();//用于存放已经被纳入结果集的节点
                   array_push($nodeStack,0);
                   $resStack= array();//用于存放结果路径,格式0=>ij,1=>jk
                   $curNodeNum= count($nodeStack);
                   //Prim算法中获取所有节点后即完成算法
                   while($curNodeNum< $nodeNum){
                            $curMin= 999;
                            $tmpArr= array();//暂存中间结果信息
                            $k= 0;//暂存节点替换信息,一轮内如果有新的权值更小的节点,则原节点出栈 
                            foreach($nodeStackas $curNode){//每次foreach从结果集中取一个点
                                     for($i=0;$i<$nodeNum;$i++){
                                               if(in_array($curNode,$nodeStack) && in_array($i, $nodeStack)){
                                                        continue;//如果两个节点都已经在结果集,则进入下一轮循环
                                               }
                                               if($arrTree[$curNode][$i]< $curMin){                                         
                                                        if($k> 0){
                                                                 //nodestack是用于存 结果集的,因此如果再次进到这个if,
                                                                 //说明上次进结果集的是暂存的内容,需要清除
                                                                 array_pop($nodeStack);
                                                        }
                                                        $curMin= $arrTree[$curNode][$i];
                                                        $tmpArr[$curMin]= $curNode.$i;//拼接成ij的形式,便于确定是哪条边
                                                        array_push($nodeStack,$i);
                                                        $k++;
                                               }
                                     }                                   
                            }
                            array_push($resStack,$tmpArr[$curMin]);
                            //计数确认当前是否已经捕获所有节点
                            $curNodeNum= count($nodeStack);
                   }
                   //计算路径值
                   $sum= 0;
                   foreach($resStackas $key => $val){
                            $i= intval($val[0]);
                            $j= intval($val[1]);
                            $sum+= $arrTree[$i][$j];
                   }
                   returnarray('resRoad' => $resStack, 'resSum' => $sum);
         }
 }

$minTree = new MinTree();
$primRes = $minTree->getPrimResult();
echo '采用Prim算法,获取的最小生成树为:';
print_r($primRes['resRoad']);
echo '<br />最终的权值和为:'.$primRes['resSum'].'<br/>';

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

——written by linhxx 2017.07.09

相关阅读:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏tkokof 的技术,小趣及杂念

OpenGL ES Shading Language 2.0 参考笔记

声明 struct matStruct { vec4 ambientColor; vec4 diffuseColor; ...

441
来自专栏进击的程序猿

seq2seq模型之raw_rnn

本文是seq2seq模型的第二篇,主要是通过raw_rnn来实现seq2seq模型。 github地址是:https://github.com/zhuanxu...

822
来自专栏数值分析与有限元编程

有限元 | 梁单元有限元程序算例

之前发过一个梁单元有限元分析程序。在好友测试时发现一个问题,就是程序中的real型变量默认为kind=4,我们姑且称为单精度型。这样限制了程序的使用,在一些问题...

2668
来自专栏TechBox

数据结构与算法系列之时间复杂度前言时间复杂度算法的空间复杂度

892
来自专栏人工智能LeadAI

Python数据分析模块 | pandas做数据分析(二):常用预处理操作

在数据分析和机器学习的一些任务里面,对于数据集的某些列或者行丢弃,以及数据集之间的合并操作是非常常见的. 1、合并操作 pandas.merge pandas....

3416
来自专栏Python小屋

Python+KNN算法判断单词相似度小案例

本文代码用于判断待测单词与哪个候选单词最接近,判断标准为字母出现频次(直方图)最接近,只考虑了不小心的拼写错误,而没有考虑故意的拼写错误,例如故意把god写成d...

3244
来自专栏人工智能LeadAI

你听过算法也是可以贪心的吗?

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。 贪心算法...

3597
来自专栏C语言及其他语言

优秀题解【图的遍历——深度优先搜索】

解题思路: (1)总思路:在图中任意选取一个顶点开始(题目要求编号为0开始),访问该顶点,并把该顶点设置为已访问

562
来自专栏程序生活

贪心算法总结贪心算法基本思路算法实现实例分析参考

贪心算法 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。...

5344
来自专栏自然语言处理

程序员眼中的统计学5

定义:若具有性质A的事件有m个,具有性质B的事件有n个,则具有性质A或性质B的事件有m+n个。

653

扫描关注云+社区