时时商务社区

标题: PHP实现克鲁斯卡尔算法实例解析 [打印本页]

作者: bewin83 时间: 2018-2-14 05:55

         本文实例展示了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;
  }
}
?>
感兴趣的读者可以调试运行一下本文克鲁斯卡尔算法实例，相信会有新的收获。


您可能感兴趣的文章:

php实现的常见排序算法汇总

PHP大转盘中奖概率算法实例

PHP冒泡算法详解（递归实现）

php计算两个整数的最大公约数常用算法小结

PHP树的深度编历生成迷宫及A*自动寻路算法实例分析

PHP贪婪算法解决0-1背包问题实例分析

php约瑟夫问题解决关于处死犯人的算法

PHP实现通过Luhn算法校验信用卡卡号是否有效

php实现猴子选大王问题算法实例

欢迎光临时时商务社区 (http://bbs.4435.cn/)