PHP实现克鲁斯卡尔算法实例解析
程序员文章站
2022-07-21 22:14:16
本文实例展示了php实现的格鲁斯卡尔算法(kruscal)的实现方法,分享给大家供大家参考。相信对于大家的php程序设计有一定的借鉴价值。
具体代码如下:
&l...
本文实例展示了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; } } ?>
感兴趣的读者可以调试运行一下本文克鲁斯卡尔算法实例,相信会有新的收获。
下一篇: PHP删除数组中空值的方法介绍