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

前端技术 2023/09/01 PHP

本文实例展示了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;
  }
}
?>

感兴趣的读者可以调试运行一下本文克鲁斯卡尔算法实例，相信会有新的收获。

本文地址：https://www.stayed.cn/item/2364

转载请注明出处。

本站部分内容来源于网络,如侵犯到您的权益,请 联系我

我的博客

人生若只如初见，何事秋风悲画扇。

我的标签

随笔档案