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

本文实例展示了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());
    ?>

edge.php文件代码如下：

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

感兴趣的读者可以调试运行一下本文克鲁斯卡尔算法实例，相信会有新的收获。