欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  php教程

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

程序员文章站 2024-02-21 16:22:22
...

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

本文实例展示了PHP实现的格鲁斯卡尔算法(kruscal)的实现方法,分享给大家供大家参考。相信对于大家的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());
?>

edge.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 $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 = $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 getWeight() getWeight()) {
        $left[] = $item[$i];
      } else {
        $right[] = $item[$i];
      }
    }
    $return = $this->unio($left, $right, $key);
    $k = 0;
    for ($i = $begin; $i 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
#include
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 {
p[i]=i;
rank[i]=0;
}
}
bool cmp(edge a,edge b)
{
return a.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 {
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 {
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 {
printf("%d %d\n",e[cho[j]].u,e[cho[j]].v);
}
return 0;
}...余下全文>>
 

怎实现克鲁斯卡尔算法?

最好结合具体题目实现,我这里有个题目,里面有完整的代码,慢慢理解就是了 blog.csdn.net/...751786
里面还有很多,感兴趣也可以看看
 

相关标签: PHP 算法