PHP实现克鲁斯卡尔算法实例解析_php技巧

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

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 = $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();    <i>1本文来#源gaodai$ma#com搞$代*码*网</i><pre>搞代gaodaima码

$right = array(); for ($i = ($begin + 1); $i getWeight() getWeight()) { $left[] = $item[$i]; } else { $right[] = $item[$i]; } } $return = $this->unio($left, $right, $key); $k = 0; for ($i = $begin; $i 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; }}?>