巅云智能建站平台搭建版(创业流派版)火爆上线,毕生受权!新增:文章智能收罗+全站真静态打包+都会分站+智能小法式+不法词过滤+H5自顺应+智能链词等功效功效概况
赞助文档Help

PHP完成克鲁斯卡尔算法实例剖析

一佰互联网站建造(www.taishanly.com) 宣布日期 2020-04-28 13:46:31 阅读数: 97

本文实例展现了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() . "
";
      }
    }
  }
  //查找子树的尾结点
  private function findRoot($node) {
    while ($this->krus[$node] != "0") {
      $node = $this->krus[$node];
    }
    return $node;
  }
}
?> 

感乐趣的读者能够调试运转一下本文克鲁斯卡尔算法实例,信任会有新的收成。

一佰互联是天下着名建站品牌办事商,咱们有九年、网站建造、网页设想、php开辟和域名注册及假造主机办事经历,供给的办事更是天下着名。比来几年来还整合团队上风自立开辟了可视化多用户”“3.0平台版,拖拽排版网站建造设想,轻松完成pc站、手机微网站、小法式、APP一体化全网营销网站扶植 ,已胜利的为天下上百家收集公司供给自助建站平台搭建办事。

相干消息more

28
04月
php从csv文件读取数据并输入到网页的体例

本文实例报告了php从csv文件读取数据并输入到网页的体例。分享给大师供大师参考。详细完成体例以下:<?php$fp = fo... >>概况

23
04月
详解Linux 下开辟微信小法式装置开辟东西

详解Linux 下开辟微信小法式装置开辟东西1.git clone http://github.com/yuan1994/wechat_w... >>概况

26
03月
2019淘宝纵贯车黑车手艺,老司机带你实操3

简介:大师好,我是纵贯车操盘手老白,淘宝纵贯车的黑车手艺比来被大师炒的满城风雨,良多人都在问黑车事实若何操纵?本篇文章就详细讲授黑车的操纵手... >>概况

20
04月
检测阅读器是不是撑持html5视频的代码

在http://www.w3school.com.cn进修html5的时辰,看到一个检测您的阅读器是不是撑持 HTML5 视频的体例:运转结果... >>概况

高端网站扶植

美工统筹SEO,为企业电子商务营销助力!

德律风:

023-85725751
建站

产物

域名注册 假造主机 云办事器 企业邮局
智能建站 APP打包 微站/小法式 创业平台
网站推行 媒体营销 智能收罗 AI机械人
400德律风 短信营销 店销机械人
私家定制 流派网站