PHP数据结构(十一)——图的连通性问题与最小生成树算法(2)
(原创内容,转载请注明来源,谢谢)
再次遇到微信公众号限制字数3000字的问题。因此将Kruskal算法放于本文中进行描述。本文接上一篇文章。
4、Kruskal算法
1)该算法的时间复杂度为O(eloge),e表示边的数目,即该算法的时间复杂度和顶点数目无关。该算法适用于边数较少的稀疏网。
2)算法内容
假设N={V, {E}}是连通网,算法初始状态为包含图中的所有的点,没有边的T=(V, {})开始,图中的每一个顶点自成一个连通分量,重复执行以下操作:
在E中选一条代价最小的边,如果此边符合该边依附在两个不同的连通分量上的要求,则将此边加入T,否则找代价第二小的边。以此类推,直至T中所有顶点都落在同一个连通分量上位置。则TE包含n-1条边,T=(V, {TE})是最小生成树。
该算法需要引入一个二维数组,记录任意两个顶点之间的权值,如果两个顶点没有连接,则权值为无穷大。
5、总结
Prim算法和Kruskal算法,区别在于从顶点切入还是从边切入。因此,当顶点较多但边相对较少时,可以使用Kruskal算法;反之,顶点较少而边相对较多时,可以使用Prim算法。两个算法都需要引入一个二维数组,用于存储任意两点间的权值,当两点没有连接时,权值为无穷大,表示该点无法直接到达另一点。
6、编码实现
PHP实现Prim算法和Kruskal算法的运行结果如下:
//Kruskal算法:以边为依据生成最小生成树
publicfunction getKruskalResult(){
//进行数组转换,将siteWeigh转成一维数组'ij'=>weigh的形式
$arrKruskal= $this->changeArray($this->siteWeigh);
//对转换后的数组进行排序,由从小到大的序列进行排序,便于后面取权值小的边
$arrKruskal= $this->sortArray($arrKruskal);
/*Array( [0] => Array ( [line] => 41 [weigh] => 5 ) [1] => Array ( [line]=> 10 [weigh] => 10 ) [2] => Array ( [line] => 31 [weigh] => 10)
[3]=> Array ( [line] => 43 [weigh] => 10 ) [4] => Array ( [line] =>20 [weigh] => 15 )
[5]=> Array ( [line] => 40 [weigh] => 20 ) [6] => Array ( [line] =>32 [weigh] => 25 ) )*/
$nodeNum= count($arrKruskal);//获取节点数目
$resStack= array();//用于存放结果路径,格式0=>ij,1=>jk
$nodeStack= array();//判断新取的边是否在同一个连通分量
//遍历生成的数组,因为已经排好序,所以从第一个开始遍历
//如果遍历到的边,两个节点都已经纳入结果集,说明该边是冗余的边
//则该边不是最小生成树,跳过,遍历下一条
foreach($arrKruskalas $line){
$node1= $line['line'][0];//获取两个阶段的编号
$node2= $line['line'][1];
if(in_array($node1,$nodeStack) && in_array($node2, $nodeStack)){
continue;//判断两个节点都在结果集就跳过
}
array_push($resStack,$line);//边进结果集
if(!in_array($node1,$nodeStack)){
array_push($nodeStack,$node1);//边的节点进结果集
}
if(!in_array($node2,$nodeStack)){
array_push($nodeStack,$node2);
}
}
//计算权值
$sum= 0;
foreach($resStackas $nodeNum => $node){
$sum+= $node['weigh'];
}
returnarray('resRoad' => $resStack, 'resSum' => $sum);
}
//提供给kruskal算法的数组转换,将二维数组转换成一维数组
privatefunction changeArray($arrToChange){
$res= array();
$nodeNum= count($arrToChange);
for($i=0;$i<$nodeNum;$i++){
//因为数组是三角对称的,只需要遍历半边即可
//并且i==j即单个顶点的情况不需要遍历
for($j=0;$j<$i;$j++){
if(999== $arrToChange[$i][$j]){
continue;//不存在的线不需要遍历
}
//$i.$j表示边ij
$res[]= array('line' => $i.$j, 'weigh' => $arrToChange[$i][$j]);
}
}
return$res;
}
//提供给kruskal算法的数组排序,采用快速排序的思想
privatefunction sortArray($arrToSort){
$res= array();
$nodeNum= count($arrToSort);//获取节点总数
$firstNode= array_shift($arrToSort);//取第一个节点,用于快速排序
$leftSmallArr= array();//存放比第一个节点小的
$rightBigArr= array();//存放比第一个节点大的
foreach($arrToSortas $node){
if($node['weigh']< $firstNode['weigh']){
array_push($leftSmallArr,$node);//小于第一个节点的分到左边数组,否则去右边数组
}else{
array_push($rightBigArr,$node);
}
}
$leftRes= array();
if(count($leftSmallArr)> 1){
$leftRes= $this->sortArray($leftSmallArr);//当数组多个元素,调用函数再次排序
}elseif(1 == count($leftSmallArr)){
$leftRes= $leftSmallArr;//当数组只有一个元素,则返回此元素
}else{
}
//同leftRes
$rightRes= array();
if(count($rightBigArr)>= 1){
$rightRes= $this->sortArray($rightBigArr);
}elseif(1 == count($rightBigArr)){
$rightRes= $rightBigArr;
}else{
}
returnarray_merge($leftRes, array($firstNode), $rightRes);
}
$minTree = new MinTree();
$kruskalRes = $minTree->getKruskalResult();
echo '采用kruskal算法,获取的最小生成树为:';
print_r($kruskalRes['resRoad']);
echo '<br />最终的权值和为:'.$primRes['resSum'].'<br/>';
题外话:两种最小生成树算法,Prim以节点为切入点获取最小生成树,Kruskal以边为切入点获取最小生成树。两者实现方式较为不同,Prim算法主要以栈的思想进行解决,因此实际编码过程中进出栈的处理逻辑需要理清楚;Kruskal重在排序,当每条边的长度排好时,其他问题迎刃而解。
——written by linhxx 2017.07.09