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;
}
}
?>
感兴趣的读者可以调试运行一下本文克鲁斯卡尔算法实例，相信会有新的收获。
相关推荐
-
PHP大转盘中奖概率算法实例
本文实例讲述了PHP大转盘中奖概率算法的实现方法,分享给大家供大家参考.具体如下: 大转盘是最近很多线上网动中一个比较有意思的东西了,下面我们就来看看这个大转盘中奖概率算法与例子,希望对各位有所帮助. 这是一个APP客户端有大转盘抽奖算法,具体如何抽奖当然在我们服务端实现了.下面和大家简单分享一下实现代码: 复制代码 代码如下: header("Content-type: text/html; charset=utf-8"); $prize_arr = array( '0' =>
-
PHP冒泡算法详解（递归实现）
实现 复制代码 代码如下: /* 冒泡算法(递归实现) */ function maoPao($array, $index=0) { $count = count($array); if(($count-1) <= $index) return $array; for($i=$count-1; $i>$index; $i-- ) { if($array[$i] < $array[$i-1]) {
-
php约瑟夫问题解决关于处死犯人的算法
本文实例讲述了php约瑟夫问题解决关于处死犯人的算法.分享给大家供大家参考.具体分析如下: 古代某法官要判决IV个犯人的死刑,他有一条荒唐的法律将犯人站成一个圆圈,从第s个人开始数起,每到第D个人就拉出来处死,然后再数D个,再拉出来处决-- 直到剩下最后一个可以赦免. function getNum($n,$m){ //用于把所有的数存到数组初始化 $a = array(); //遍历,存入数组 for($i=1;$i<=$n;$i++){ $a[$i] = $i; } //指针归0 reset
-
PHP树的深度编历生成迷宫及A*自动寻路算法实例分析
本文实例讲述了PHP树的深度编历生成迷宫及A*自动寻路算法.分享给大家供大家参考.具体分析如下: 有一同事推荐了三思的迷宫算法,看了感觉还不错,就转成php 三思的迷宫算法是采用树的深度遍历原理,这样生成的迷宫相当的细,而且死胡同数量相对较少! 任意两点之间都存在唯一的一条通路. 至于A*寻路算法是最大众化的一全自动寻路算法 废话不多说,贴上带代码 迷宫生成类: 复制代码 代码如下: class Maze{ // Maze Create private $_w; priv
-
php计算两个整数的最大公约数常用算法小结
本文实例讲述了php计算两个整数的最大公约数常用算法.分享给大家供大家参考.具体如下: 复制代码 代码如下: <?php //计时,返回秒 function microtime_float () { list( $usec , $sec ) = explode ( " " , microtime ()); return ((float) $usec + (float) $sec ); } /////////////////////////////////
-
php实现猴子选大王问题算法实例
本文实例讲述了php实现猴子选大王问题算法.分享给大家供大家参考.具体分析如下: 一.问题: n只猴子围坐成一个圈,按顺时针方向从1到n编号. 然后从1号猴子开始沿顺时针方向从1开始报数,报到m的猴子出局,再从刚出局猴子的下一个位置重新开始报数, 如此重复,直至剩下一个猴子,它就是大王. 设计并编写程序,实现如下功能: (1) 要求由用户输入开始时的猴子数$n.报数的最后一个数$m. (2) 给出当选猴王的初始编号. 二.解决方法: /** * @param int $n 开始时的猴子数
-
php实现的常见排序算法汇总
本文汇总了常见的php排序算法,在进行算法设计的时候有不错的借鉴价值.现分享给大家供参考之用.具体如下: 一.插入排序 用文字简单的描述,比如说$arr = array(4,2,4,6,3,6,1,7,9); 这样的一组数字进行顺序排序: 那么,首先,拿数组的第二个元素和第一元素比较,假如第一个元素大于第二元素,那么就让两者位置互换,接下来,拿数组的第三个元素,分别和第二个,第一个元素比较,假如第三个元素小,那么就互换.依次类推.这就是插入排序,它的时间频度是:1+2+...+(n-1)=(n^
-
PHP实现通过Luhn算法校验信用卡卡号是否有效
本文实例讲述了PHP实现通过Luhn算法校验信用卡卡号是否有效的方法.分享给大家供大家参考.具体实现方法如下: $numbers = "49927398716 49927398717 1234567812345678 1234567812345670"; foreach (split(' ', $numbers) as $n) echo "$n is ", luhnTest($n) ? 'valid' : 'not valid', '</br>'; fu
-
PHP贪婪算法解决0-1背包问题实例分析
本文实例讲述了PHP贪婪算法解决0-1背包问题的方法.分享给大家供大家参考.具体分析如下: 贪心算法解决0-1背包问题,全局最优解通过局部最优解来获得!比动态规划解决背包问题更灵活! //0-1背包贪心算法问题 class tanxin{ public $weight; public $price; public function __construct($weight=0,$price=0) { $this->weight=$weight; $this->price=$price; } }
-
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' =>
-
Java语言基于无向有权图实现克鲁斯卡尔算法代码示例
所谓有权图,就是图中的每一条边上都会有相应的一个或一组值.通常情况下,这个值只是一个数字 如:在交通运输网中,边上的权值可能表示的是路程,也可能表示的是运输费用(显然二者都是数字).不过,边上的权值也有可能是其它东西,比如说是一个字符串,甚至是一个更加复杂的数据包,里面集合了更多的数据 克鲁斯卡尔算法的核心思想是:在带权连通图中,不断地在边集合中找到最小的边,如果该边满足得到最小生成树的条件,就将其构造,直到最后得到一颗最小生成树. 克鲁斯卡尔算法的执行步骤: 第一步:在带权连通图中,将边的权值
-
Java8 HashMap扩容算法实例解析
这篇文章主要介绍了Java8 HashMap扩容算法实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 Java8的HashMap扩容过程主要就是集中在resize()方法中 final Node<K,V>[] resize() { // ...省略不重要的 } 其中,当HashMap扩容完毕之后,需要对原有的数据进行转移.因为容量变大了,部分元素的位置因此要变更,因而出现了下面的这个转移过程. 转移过程大致是:依次从旧数组里取值,然后从
-
python有序查找算法 二分法实例解析
这篇文章主要介绍了python有序查找算法 二分法实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 二分法是一种快速查找的方法,时间复杂度低,逻辑简单易懂,总的来说就是不断的除以2除以2... 但是需要注意: 待查找的序列区间单调有序 例如需要查找有序数组arr里面的某个关键字key的位置,那么首先确认arr的中位数或者中点center,下面分为三种情况: 假如arr[center]>key,说明key在arr中心左边范围: 假如arr[
-
LRU算法及Apache LRUMap源码实例解析
目录 1. 什么是LRU 1.1 自定义实现LRU的要求 1.2 Apache LRUMap示例 1.2.1 pom依赖 1.2.2 demo 2. 源码解析 2.1 设计 2.2 数据结构 2.3 方法解析put get remove 2.3.1 get方法 2.3.2 remove方法 2.3.3 put方法 3. 总结 1. 什么是LRU LRU(least recently used) : 最近最少使用 LRU就是一种经典的算法,在容器中,对元素定义一个最后使用时间,当新的元素写入的时候
-
Java对象的XML序列化与反序列化实例解析
上一篇文章我们介绍了java实现的各种排序算法代码示例,本文我们看看Java对象的xml序列化与反序列化的相关内容,具体如下. XML是一种标准的数据交换规范,可以方便地用于在应用之间交换各类数据.如果能在Java对象和XML文档之间建立某种映射,例如Java对象的XML序列化和反序列化,那么就可以使Java的对象方便地与其他应用进行交换. java.beans包里面有两个类XMLEncoder和Decoder,分别用于将符合JabaBeans规范的Java对象以XML方式序列化和反序列化.以下
-
Java使用异或运算实现简单的加密解密算法实例代码
Java简单的加密解密算法,使用异或运算 实例1: package cn.std.util; import java.nio.charset.Charset; public class DeEnCode { private static final String key0 = "FECOI()*&<MNCXZPKL"; private static final Charset charset = Charset.forName("UTF-8"); pr
-
numpy.random.seed()的使用实例解析
这个函数的使用方法,已经有前辈讲解过了,只是自己在测试的时候有一些思考,所以便写了这篇博客.下面是前辈文章的原话: seed( ) 用于指定随机数生成时所用算法开始的整数值,如果使用相同的seed( )值,则每次生成的随即数都相同,如果不设置这个值,则系统根据时间来自己选择这个值,此时每次生成的随机数因时间差异而不同. 编写如下第一份代码: from numpy import * num=0 while(num<5): random.seed(5) print(random.random())
-
Java编程通过匹配合并数据实例解析（数据预处理）
本文研究的主要是Java编程通过匹配合并数据(数据预处理)的相关内容,具体如下. 数据描述 以下程序是对如下格式的数据进行合并处理. 这个表的每一行表示用户id及用户的特征.其中,一个用户只有一个特征向量,即第一列不会重复. 这张表的第一列,表示用户的id,第二列表示用户所看的电影,第三列表示用户对电影的打分(1-13分),第四列表示用户对电影的打分,但分值范围是1-5分. 问题描述 在做数据预处理时,如何将第二张表添加上用户特征呢?其实,方法很简单,将第二张表的用户id与第一张表的用户id进行
-
PHP折半（二分）查找算法实例分析
本文实例讲述了PHP折半(二分)查找算法.分享给大家供大家参考,具体如下: 折半查询只适用于已经按照正序或者逆序排序的数组,字符串等: 算法: 先取数组的中间位置,无中间位置,则向下取整: 从中间进行折半,大小判断,进入前半段或者后半段: 再对前半段或者后半段进行同样的折半查询, 直到查询到匹配的字符,才停止(本例用break,如果置于函数中,return即可) php实现的代码如下: <?php $arr = array(1,2,3,4,5,6,7,8,9,10);//数组 $key = 4;