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

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