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