本文實例展示了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;
}
}
?>
感興趣的讀者可以調試運行一下本文克魯斯卡爾算法實例，相信會有新的收獲。
你確定要用鄰接表嗎？因為在克魯斯卡爾算法裡只需要存儲邊及費用，用鄰接表意義不大，還不好排序。
以下給出並查集實現的克魯斯卡爾算法，求解生成網絡的最小費用，並輸出生成網絡裡的路徑。
#include<iostream>
#include<algorithm>
using namespace std;
int p[1001],rank[1001];
int cho[1001];
struct edge
{
int u,v,w;//u表示起始點編號，v表示終點編號，w表示該路徑費用
}e[15001];
int n,m;//n表示點的個數，m表示路徑數
void Init()
{
int i;
for(i=1;i<=n;i++)
{
p[i]=i;
rank[i]=0;
}
}
bool cmp(edge a,edge b)
{
return a.w<b.w;
}
int Find(int t)
{
if(p[t]!=t)
{
p[t]=Find(p[t]);
}
return p[t];
}
int Union(int a,int b)
{
int x,y;
x=Find(a);
y=Find(b);
if(rank[x]>rank[y])
{
p[y]=x;
}
else
{
p[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
int i,j;
for(i=0;i<m;i++)
{
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
}
Init();
sort(e,e+m,cmp);
int cnt=0,ans=0;
for(i=0;i<m;i++)
{
if(Find(e[i].u)!=Find(e[i].v))
{
cnt++;
ans+=e[i].w;
Union(e[i].u,e[i].v);
cho[++cho[0]]=i;
if(cnt==n-1)
break;
}
}
printf("%d\n",ans);
for(j=1;j<=cho[0];j++)
{
printf("%d %d\n",e[cho[j]].u,e[cho[j]].v);
}
return 0;
}...余下全文>>
最好結合具體題目實現，我這裡有個題目，裡面有完整的代碼，慢慢理解就是了 blog.csdn.net/...751786
裡面還有很多，感興趣也可以看看
