PHP实现克鲁斯卡尔算法

PHP实现的格鲁斯卡尔算法（kruscal），如下代码：

    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()); 
?> 
 

 
    //边集数组的边类 
    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 $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; 
    } 
} 
?>