PHP数据结构（十一） ——图的连通性问题与最小生成树算法（1）
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