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 = 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;
    }
}


?>