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

本文实例展示了PHP实现的格鲁斯卡尔算法（kruscal）的实现方法，分享给大家供大家参考。相信对于大家的PHP程序设计有一定的借鉴价值。
具体代码如下：

<?phprequire "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（） . "
";}}}//查找子树的尾结点private function findRoot（$node） {while （$this->krus[$node] ！= "0"） {$node = $this->krus[$node];}return $node;}}?>

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