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; } } ?>
感兴趣的读者可以调试运行一下本文克鲁斯卡尔算法实例,相信会有新的收获。