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

本文实例展示了PHP实现的格鲁斯卡尔算法（kruscal）的实现方法，分享给大家供大家参考。相信对于大家的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());?>edge。
php文件代码如下：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(); $right = array(); for ($i = ($begin + 1); $igetWeight()getWeight()) { $left[] = $item[$i]; } else { $right[] = $item[$i]; } } $return = $this->unio($left, $right, $key); $k = 0; for ($i = $begin; $ikrus = 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; }}?>感兴趣的读者可以调试运行一下本文克鲁斯卡尔算法实例，相信会有新的收获。