PHP网站制作之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    //边集数组的边类    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;    } } ?>

复制代码