PHP实现克鲁斯卡尔(kruscal)算法

zhaolu

<?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 = new Edge($a, $b);
print_r($test->kruscal());
?>

<?php
/**
* 边集数组
*
* @author zhaojiangwei
* @since 2011/11/4 16:09
*
*/
//边集数组的边类
class EdgeArc{
private $begin;//起始点
private $end;//结束点
private $weight;//权值
public function EdgeArc($begin, $end, $weight){
$this->begin = $begin;
$this->end = $end;
$this->weight = $weight;
}
public function getBegin(){
return $this->begin;
}
public function getEnd(){
return $this->end;
}
public function getWeight(){
return $this->weight;
}
}

class Edge{
//边集数组实现图
private $vexs;//顶点集合
private $arc;//边集合
private $arcData;//要构建图的边信息
private $krus;//kruscal算法时存放森林信息
public function Edge($vexsData, $arcData){
$this->vexs = $vexsData;
$this->arcData = $arcData;
$this->createArc();
}
//创建边
private function createArc(){
foreach($this->arcData as $key=>$value){
$key = str_split($key);
$this->arc[] = new EdgeArc($key[0], $key[1], $value);
}
}
//对边数组按权值排序
public function sortArc(){
$this->quicklySort(0, count($this->arc) - 1, $this->arc);
return $this->arc;
}
//采用快排
private function quicklySort($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);
}
private function excuteSort($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);
}
private function unio($left, $right, $key){
return array_merge($left, array($key), $right);
}
//kruscal算法
public function kruscal(){
$this->krus = array();
$this->sortArc();
foreach($this->vexs as $value){
$this->krus[$value] = "0";
}
foreach($this->arc as $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";
}
}
}
//查找子树的尾结点
private function findRoot($node){
while($this->krus[$node] != "0"){
$node = $this->krus[$node];
}
return $node;
}
}

?>