PHP实现克鲁斯卡尔算法实例解析
本文实例展示了PHP实现的格鲁斯卡尔算法（kruscal）的实现方法，分享给大家供大家参考。相信对于大家的PHP程序设计有一定的借鉴价值。
具体代码如下：
<?php require'edge.php'; $a=array( 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i' ); $b=array( 'ab'=>'10', 'af'=>'11', 'gb'=>'16', 'fg'=>'17', 'bc'=>'18', 'bi'=>'12', 'ci'=>'8', 'cd'=>'22', 'di'=>'21', 'dg'=>'24', 'gh'=>'19', 'dh'=>'16', 'de'=>'20', 'eh'=>'7', 'fe'=>'26' ); $test=newEdge($a,$b); print_r($test->kruscal()); ?>
edge.php文件代码如下：
<?php
//边集数组的边类
classEdgeArc{
private$begin;//起始点
private$end;//结束点
private$weight;//权值
publicfunctionEdgeArc($begin,$end,$weight){
$this->begin=$begin;
$this->end=$end;
$this->weight=$weight;
}
publicfunctiongetBegin(){
return$this->begin;
}
publicfunctiongetEnd(){
return$this->end;
}
publicfunctiongetWeight(){
return$this->weight;
}
}
classEdge{
//边集数组实现图
private$vexs;//顶点集合
private$arc;//边集合
private$arcData;//要构建图的边信息
private$krus;//kruscal算法时存放森林信息
publicfunctionEdge($vexsData,$arcData){
$this->vexs=$vexsData;
$this->arcData=$arcData;
$this->createArc();
}
//创建边
privatefunctioncreateArc(){
foreach($this->arcDataas$key=>$value){
$key=str_split($key);
$this->arc[]=newEdgeArc($key[0],$key[1],$value);
}
}
//对边数组按权值排序
publicfunctionsortArc(){
$this->quicklySort(0,count($this->arc)-1,$this->arc);
return$this->arc;
}
//采用快排
privatefunctionquicklySort($begin,$end,&$item){
if($begin<0($begin>=$end))return;
$key=$this->excuteSort($begin,$end,$item);
$this->quicklySort(0,$key-1,$item);
$this->quicklySort($key+1,$end,$item);
}
privatefunctionexcuteSort($begin,$end,&$item){
$key=$item[$begin];
$left=array();
$right=array();
for($i=($begin+1);$i<=$end;$i++){
if($item[$i]->getWeight()<=$key->getWeight()){
$left[]=$item[$i];
}else{
$right[]=$item[$i];
}
}
$return=$this->unio($left,$right,$key);
$k=0;
for($i=$begin;$i<=$end;$i++){
$item[$i]=$return[$k];
$k++;
}
return$begin+count($left);
}
privatefunctionunio($left,$right,$key){
returnarray_merge($left,array(
$key
),$right);
}
//kruscal算法
publicfunctionkruscal(){
$this->krus=array();
$this->sortArc();
foreach($this->vexsas$value){
$this->krus[$value]="0";
}
foreach($this->arcas$key=>$value){
$begin=$this->findRoot($value->getBegin());
$end=$this->findRoot($value->getEnd());
if($begin!=$end){
$this->krus[$begin]=$end;
echo$value->getBegin()."-".$value->getEnd().":".$value->getWeight()."\n";
}
}
}
//查找子树的尾结点
privatefunctionfindRoot($node){
while($this->krus[$node]!="0"){
$node=$this->krus[$node];
}
return$node;
}
}
?>
感兴趣的读者可以调试运行一下本文克鲁斯卡尔算法实例，相信会有新的收获。