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()
);
?>
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 $ar
c; //边集合
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],$ke
Y[1],$
value);
}
}
//对边数组按权值排序
public function sortArc()
{
$this->quicklySort(0,count($this->ar
C) - 1,$this->arc
);
return $this->ar
c;
}
//采用快排
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($nod
E) {
while ($this->krus[$node]
!= "0")
{
$node = $this->krus[$node];
}
return $node;
}
}
?>
