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

相关文章

来自专栏我和未来有约会

Silverlight第三方控件专题

这里我收集整理了目前网上silverlight第三方控件的专题,若果有所遗漏请告知我一下。 名称 简介 截图 telerik 商 RadC...

4025
来自专栏我和未来有约会

Kit 3D 更新

Kit3D is a 3D graphics engine written for Microsoft Silverlight. Kit3D was inita...

2536
来自专栏转载gongluck的CSDN博客

cocos2dx 打灰机

#include "GamePlane.h" #include "PlaneSprite.h" #include "BulletNode.h" #include...

5466
来自专栏飞扬的花生

jsencrypt参数前端加密c#解密

      写程序时一般是通过form表单或者ajax方式将参数提交到服务器进行验证,如何防止提交的请求不被抓包后串改,虽然无法说绝对安全却给非法提交提高了难度...

3869
来自专栏hbbliyong

WPF Trigger for IsSelected in a DataTemplate for ListBox items

<DataTemplate DataType="{x:Type vm:HeaderSlugViewModel}"> <vw:HeaderSlug...

4064
来自专栏落花落雨不落叶

canvas画简单电路图

61811
来自专栏张善友的专栏

Mix 10 上的asp.net mvc 2的相关Session

Beyond File | New Company: From Cheesy Sample to Social Platform Scott Hansel...

2577
来自专栏一个爱瞎折腾的程序猿

sqlserver使用存储过程跟踪SQL

USE [master] GO /****** Object: StoredProcedure [dbo].[sp_perfworkload_trace_s...

2060
来自专栏一个会写诗的程序员的博客

Spring Reactor 项目核心库Reactor Core

Non-Blocking Reactive Streams Foundation for the JVM both implementing a Reactiv...

2152
来自专栏跟着阿笨一起玩NET

c#实现打印功能

2762

扫码关注云+社区