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

相关文章

来自专栏吉浦迅科技

DAY18:阅读纹理内存之Layered Textures

1004
来自专栏aCloudDeveloper

算法导论第十五章 动态规划

      写在前面:从本章开始,算法导论章节进入第四部分:高级设计和分析技术。在读的过程中,可以明显感觉到本章内容跟之前章节的内容要复杂得多。这么来说,之前章...

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

回溯算法入门及经典案例剖析(初学者必备宝典)

前言 基于有需必写的原则,并且当前这个目录下的文章数量为0(都是因为我懒QAQ),作为开局第一篇文章,为初学者的入门文章,自然要把该说明的东西说明清楚,于是。。...

3404
来自专栏向治洪

图算法之bfs、dfs、prim、Dijkstra

概述 在图算法中经常要执行遍历每个顶点和每条边的操作,即图搜索。许多图算法都以图搜索为基础,如2-着色问题、连通性计算基于深度优先搜寻(depth-first ...

2466
来自专栏freesan44

python 算法开发笔记

992
来自专栏大数据挖掘DT机器学习

非主流自然语言处理:大规模语料词库自动生成

一、前言   写这篇文时,突然想到一个问题,大家的词库都是从哪来的?   之所以会这么有些意外的问,是因为从没把词库当成个事儿:平时处理微博,就用程序跑一下微博...

41212
来自专栏天天P图攻城狮

Android OpenGL开发实践 - 基于OpenGL ES 2.0的Android相机实时图片涂鸦实现思路

这篇文章将给大家讲解如何在Android系统上基于OpenGL ES 2.0来实现相机实时图片涂鸦效果,所涂内容跟随人脸出现、消失、移动、旋转及缩放,在这里,我...

1K13
来自专栏开源FPGA

基于MATLAB的RGB转YCBCR色彩空间转换

  使用MATLAB进行图片的处理十分方便,看它的名字就知道了,矩阵实验室(matrix laboratory)。一副图片的像素数据可以看成是一个二维数组一个大...

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

可视化 | Tecplot作三角形单元后处理工具

对于有限元分析的后处理,除了单的信息,还包括单元信息,比如一个单元由哪些结点组成。Tecplot可以处理的单元类型有三角形单元,四边形单元,四面体单元和六面体单...

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

浅谈我对动态规划的一点理解---大家准备好小板凳,我要开始吹牛皮了~~~

前言 作为一个退役狗跟大家扯这些东西,感觉确实有点。。。但是,针对网上没有一篇文章能够很详细的把动态规划问题说明的很清楚,我决定还是拿出我的全部家当,来跟大家分...

6917

扫码关注云+社区