PHP实现克鲁斯卡尔算法实例解析
作者:shichen2014 发布时间:2023-09-08 19:35:57
标签: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;
}
}
?>
感兴趣的读者可以调试运行一下本文克鲁斯卡尔算法实例,相信会有新的收获。
0
投稿
猜你喜欢
- 本文实例讲述了Python整型运算之布尔型、标准整型、长整型操作。分享给大家供大家参考,具体如下:#coding=utf8def integ
- 1.在使用MySQL和php的时候出现过中文乱码问题(1) 只要是gb2312,gbk,utf8等支持多字节编码的字符集都可以储存汉字,当然
- 同事在学mybatis时,遇到了一个问题就是,使用char类型字段作为查询条件时一直都查不出数据,其他类型的则可以。 使用的数据库
- MongoDB简介MongoDB 是由C++语言编写的,是一个基于分布式文件存储的开源数据库系统。在高负载的情况下,添加更多的节点,可以保证
- 1、Config命令Config命令主要用于修改SSI的默认设置。其中:Errmsg:设置默认错误信息。为了能够正常的返回用户设定的错误信息
- python中的多线程其实并不是真正的多线程,如果想要充分地使用多核CPU资源,在python中大部分情况需要使用多进程。python提供了
- 上一篇博文说了 vue3 项目的 toRefs 函数和 toRef 函数,今天就稍微总结一下 vue3 的计算属性,其实学过 vue2 的宝
- js也是可以做出狂炫的图形的,恭请超级高手分析。给大家看个例子吧。http://www.p01.org/releases/DHTML_con
- 本文实例讲述了PHP中round()函数对浮点数进行四舍五入的方法。分享给大家供大家参考。具体方法如下:语法:round(x,prec)参数
- 有一台windows服务器上跑着mysql的一些应用,现在需要将mysql的数据每天备份,并通过ftp上传到指定的存储服务器上要是在linu
- 在已知DICOM和三维模型对应掩膜的情况下,计算三维模型的体积。思路:1、计算每个体素的体积。每个体素为长方体,x,y为PixelSpaci
- python2.7wget http://www.python.org/ftp/python/2.7.6/Python-2.7.6.tar.
- Python中的frame是什么栈帧(frame)栈帧表示程序运行时函数调用栈中的某一帧。想要获得某个函数相关的栈帧,则必须在调用这个函数且
- 下面直接记录下配置主从库的操作:(本文用的是mysql5.0以上)1.在主库建立要同步的数据库,建立主库的帐号和修改主库配置首先连接上数据库
- 本文实例为大家分享了python实现图像降噪的具体代码,供大家参考,具体内容如下任务描述背景图像在数字化和传输等过程中会产生噪声,从而影响图
- 执行表扫描操作之前,将调用info()函数,以便为优化程序提供额外信息。优化程序所需的信息不是通过返回值给定的,你需填充存储引擎类的特定属性
- 1、 自定义菜单adminx.pyclass GlobalSetting(object): site_title = u'xxx后台
- random模块该模块实现了各种分布的伪随机数生成器。(包括在实数轴上计算均匀、正态(高斯)、对数正态、负指数、伽马和贝塔分布的函数)不应将
- 我就废话不多说了,大家还是直接看代码吧~注释讲解版:# Classifier exampleimport numpy as np# for
- 本文实例讲述了Python根据已知邻接矩阵绘制无向图操作。分享给大家供大家参考,具体如下:有六个点:[0,1,2,3,4,5,6],六个点之