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