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
投稿
猜你喜欢
- 这个仿msn的右下角popup提示窗口效果很久以前收集的,现在整理出来给大家分享,需要的朋友可以拿去用,特点,提示窗口内容和js代码分离容易
- 本文实例讲述了PHP实现的redis主从数据库状态检测功能。分享给大家供大家参考,具体如下:实例:<?php/** * 检测多个主从r
- 大家都在关注视觉的盛宴,西方的美学;今天就分享下,中国最为古老的美,也是身边随处可见的美学–中国汉字书法之美;古文者,仓颉做造也。仰观奎星园
- 需求:获取oracle表增量信息,发送至udp514端口,支持ip配置步骤:(1)需要的jar oracle的 odbc5.ja
- 数据库(database)MySQL 是最流行的开源数据库系统,可运行于几乎所有的操作系统平台。在《MySQL 安装》一文中详解介绍了安装步
- 假如一个页面中的文本采用的都是同样的字体、同样的字号、同样的颜色,做为读者的你能轻易的区分出哪里是标题,哪里是正文内容吗?所以通常情况下,设
- 大家都知道当任务过多,任务量过大时如果想提高效率的一个最简单的方法就是用多线程去处理,比如爬取上万个网页中的特定数据,以及将爬取数据和清洗数
- ASP木马防御: 代码如下:const adTypeBinary=1 dim jpg(1):jpg(0)=CB
- js的成员和方法好象没有private和public之分,列一下public的成员和方法成员:name 控件的名字,既这个控件的变量名(必选
- 统计在线人数是实时的吗?实现起来也比较简单,见下列代码:global.asa<SCRIPT LANGUAGE="V
- 在使用SQL Server 的过程,中由于经常需要从多个不同地点将数据集中起来或向多个地点复制数据,所以数据的导出,导入是极为常见的操作.我
- if exists (select * from dbo.sysobjects where id = object_id(N'[db
- 修改MySql Server安装目录下的 my.ini 文件,在mysqld节下加入下面一行set-variable=lower_case_
- 方法不是主流的。有一组数据,大概10万个左右,每一单位的值不会大于30000,要求按照由大到小的顺序不重复输出。参考无忧cosin的方法后(
- Composer的基本使用在项目中使用composer.json在项目中使用composer,你需要有一个composer.json文件,此
- 在cssrain整理的一个 试题集 中有这么一道题:<SCRIPT LANGUAGE="JavaScript"&g
- 在默认情况下,大多数浏览器都会将有序列表中的数字序列的与其列表文字内容显示为相同的字体。这篇快速教程将教你如何使用有序列表(ol)和段落(p
- QQ医生在广大用户心中一直以来都是清爽便捷的一款安全工具,随着QQ医生的不断发展,QQ医生团队一直在思考,怎样能够给QQ医生用户带来性能更优
- 本文实例讲述了python处理图片之PIL模块简单使用方法。分享给大家供大家参考。具体实现方法如下:#!/usr/bin/env pytho
- 本程序属于一种特别的方法。使用范围比较有限,而且有一定的危险性。借鉴了asp后门里的一些方法。由于读取某IP的网卡MAC地址本程序通过调用a