<?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());
?>
<?php
/**
* 边集数组
*
* @author zhaojiangwei
* @since 2011/11/4 16:09
*
*/
//边集数组的边类
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;
}
}
?>
分享到:
相关推荐
Kruskal算法是一种用于解决图论中的最小生成树问题的经典算法,由约瑟夫·克拉克·克鲁斯卡尔在1956年提出。它通过贪心策略选择边,始终选择当前未加入树的边中权值最小的一条,并确保这条边不会形成环路。以下是对...
最后,Edge类中实现了kruscal算法方法,该方法返回一个最小生成树的结果。 实例中定义了一个名为“edge.php”的文件,其中包含了Edge类和EdgeArc类的定义。在主文件中首先引入了edge.php文件,定义了顶点数组a和边...
在`KruskalMST`文件中,可以找到实现克鲁斯卡尔算法的C++代码,包括边的结构体定义、并查集的实现以及算法的主逻辑。 **2. Prim's Algorithm(普里姆算法)** 普里姆算法从一个顶点开始,逐步添加边,使得每次添加...
在上面的代码中,UndirectedGraph 类的 Kruscal 函数实现了 Kruscal 算法,该函数首先将图中的所有边排序,然后逐步添加边,直到生成树的权值最小。在添加每条边时,使用 UnionSet 类来判断是否会形成环,如果不会...
在给出的代码中,最小生成树的实现采用了克鲁斯卡尔(Kruskal)算法。克鲁斯卡尔算法的基本思想是按边的权重从小到大排序,然后依次选择未形成环的边加入到当前的生成树中。为了避免在添加边时形成环,我们需要用到...
克鲁斯卡尔算法(Kruscal) (5)求关节点和重连通分量(Get_artical) (6)求最短路径 弗洛伊德算法(shortpath_Floyd) 迪杰斯特拉算法(shortpath_DIJ) 9. 存储管理 (1)边界标识法 (Boundary_tag_method...
克鲁斯卡尔算法(Kruscal) (5)求关节点和重连通分量(Get_artical) (6)求最短路径 弗洛伊德算法(shortpath_Floyd) 迪杰斯特拉算法(shortpath_DIJ) 9. 存储管理 (1)边界标识法 (Boundary_tag_method...
克鲁斯卡尔算法(Kruscal) (5)求关节点和重连通分量(Get_artical) (6)求最短路径 弗洛伊德算法(shortpath_Floyd) 迪杰斯特拉算法(shortpath_DIJ) 9. 存储管理 (1)边界标识法 (Boundary_tag_method...
克鲁斯卡尔算法(Kruscal) (5)求关节点和重连通分量(Get_artical) (6)求最短路径 弗洛伊德算法(shortpath_Floyd) 迪杰斯特拉算法(shortpath_DIJ) 9. 存储管理 (1)边界标识法 (Boundary_tag_method...
以数据结构中的“最小生成树”教学内容为例,翻转课堂的应用可以这样实施:首先,教师制作关于普里姆(Prim)算法和克鲁斯卡尔(Kruscal)算法的教学视频,并设置相关的在线测试题目。学生在课前观看视频,并完成在线...
克鲁斯卡尔算法(Kruscal) (5)求关节点和重连通分量(Get_artical) (6)求最短路径 弗洛伊德算法(shortpath_Floyd) 迪杰斯特拉算法(shortpath_DIJ) 9. 存储管理 (1)边界标识法 (Boundary_tag_method...
克鲁斯卡尔算法(Kruscal) (5)求关节点和重连通分量(Get_artical) (6)求最短路径 弗洛伊德算法(shortpath_Floyd) 迪杰斯特拉算法(shortpath_DIJ) 9. 存储管理 (1)边界标识法 (Boundary_tag_...