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

前端之家收集整理的这篇文章主要介绍了PHP实现克鲁斯卡尔算法实例解析前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

本文实例展示了PHP实现的格鲁斯卡尔算法(kruscal)的实现方法分享给大家供大家参考。相信对于大家的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()); ?>

edge.PHP文件代码如下:

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,&$item) { if ($begin < 0($begin >= $end)) return; $key = $this->excuteSort($begin,$item); $this->quicklySort(0,$key - 1,$item); $this->quicklySort($key + 1,$item); } private function excuteSort($begin,&$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,$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; } } ?>

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

猜你在找的PHP相关文章