PHP implementation of Kruskal algorithm example analysis, Kruskal algorithm example

PHP implementation of Kruskal algorithm example analysis, Kruskal algorithm example_PHP tutorial

WBOY

Release： 2016-07-13 10:20:10

Original

857 people have browsed it

PHP implementation of Kruskal algorithm example analysis, Kruskal algorithm example

The example in this article shows the implementation method of Kruscal algorithm (kruscal) implemented in PHP, and is shared with everyone for your reference. I believe it has certain reference value for everyone's PHP program design.

The specific code is as follows:

<&#63;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());
&#63;>

Copy after login

edge.php file code is as follows:

<&#63;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;
  }
}
&#63;>

Copy after login

Interested readers can debug and run the Kruskal algorithm example in this article. I believe there will be new gains.

Kruskal’s Algorithm

Are you sure you want to use adjacency list? Because in Kruskal's algorithm only edges and costs need to be stored, using adjacency lists makes little sense and is not easy to sort.
The following is the Kruskal algorithm implemented by union lookup, which solves the minimum cost of generating the network and outputs the path in the generated network.
#include
#include
using namespace std;
int p[1001],rank[1001];
int cho[1001];
struct edge
{
int u,v,w;//u represents the starting point number, v represents the end point number, w represents the cost of the path
}e[15001];
int n,m; //n represents the number of points, m represents the number of paths
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}
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<=cho[0];j++)
{
printf("%d %d\n",e[cho[j]].u,e[cho[j]].v);
}
return 0;
}.. .The rest of the full text>>

How to implement Kruskal's algorithm?

It’s best to combine it with specific topics. I have a topic here, which has a complete code. Just understand it slowly.blog.csdn.net/...751786
There are many more in it. If you are interested, you can read it. Look