仓酷云

标题: PHP网站制作之邻接矩阵prim:php完成图的邻接矩阵及普... [打印本页]

作者: 海妖 时间: 2015-2-3 23:31
标题: PHP网站制作之邻接矩阵prim:php完成图的邻接矩阵及普...
把例子全部敲进去试验，完成一遍以后就会有心得了，因为你会发现为啥我的程序和书上的一模一样就是结果不正确。新手学习的时候必须承认，不容易，因为我也是过来人，你会发现原来有那么多常用的语句，函数都要记。
<?php
require 'mgraph.php';
$a = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i');
$b = array('ab'=>'10', 'af'=>'11', 'bg'=>'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 mgraph($a, $b);
print_r($test->prim());
?>
mgraph.php
<?php
/**
* php 完成图邻接矩阵
*
* @author zhaojiangwei
* @since 2011/10/31 17:23
*/
class mgraph{
private $vexs; //极点数组
private $arc; //边邻接矩阵,即二维数组
private $arcdata; //边的数组信息
private $direct; //图的类型(无向或有向)
private $haslist; //测验考试遍用时存储遍历过的结点
private $queue; //广度优先遍用时存储孩子结点的队列,用数组仿照
private $infinity = 65535;//代表无量,即两点无毗连,建带权值的图时用,本示例不带权值
private $primvexs; //prim算法时保留极点
private $primarc; //prim算法时保留边
private $krus;//kruscal算法时保留边的信息
public function mgraph($vexs, $arc, $direct = 0){
$this->vexs = $vexs;
$this->arcdata = $arc;
$this->direct = $direct;
$this->initalizearc();
$this->createarc();
}
private function initalizearc(){
foreach($this->vexs as $value){
foreach($this->vexs as $cvalue){
$this->arc[$value][$cvalue] = ($value == $cvalue ? 0 : $this->infinity);
}
}
}
//创立图 $direct:0暗示无向图,1暗示有向图
private function createarc(){
foreach($this->arcdata as $key=>$value){
$strarr = str_split($key);
$first = $strarr[0];
$last = $strarr[1];
$this->arc[$first][$last] = $value;
if(!$this->direct){
$this->arc[$last][$first] = $value;
}
}
}
//floyd算法
public function floyd(){
$path = array();//途径数组
$distance = array();//间隔数组
foreach($this->arc as $key=>$value){
foreach($value as $k=>$v){
$path[$key][$k] = $k;
$distance[$key][$k] = $v;
}
}
for($j = 0; $j < count($this->vexs); $j ++){
for($i = 0; $i < count($this->vexs); $i ++){
for($k = 0; $k < count($this->vexs); $k ++){
if($distance[$this->vexs[$i]][$this->vexs[$k]] > $distance[$this->vexs[$i]][$this->vexs[$j]] + $distance[$this->vexs[$j]][$this->vexs[$k]]){
$path[$this->vexs[$i]][$this->vexs[$k]] = $path[$this->vexs[$i]][$this->vexs[$j]];
$distance[$this->vexs[$i]][$this->vexs[$k]] = $distance[$this->vexs[$i]][$this->vexs[$j]] + $distance[$this->vexs[$j]][$this->vexs[$k]];
}
}
}
}
return array($path, $distance);
}
//djikstra算法
public function dijkstra(){
$final = array();
$pre = array();//要查找的结点的前一个结点数组
$weight = array();//权值和数组
foreach($this->arc[$this->vexs[0]] as $k=>$v){
$final[$k] = 0;
$pre[$k] = $this->vexs[0];
$weight[$k] = $v;
}
$final[$this->vexs[0]] = 1;
for($i = 0; $i < count($this->vexs); $i ++){
$key = 0;
$min = $this->infinity;
for($j = 1; $j < count($this->vexs); $j ++){
$temp = $this->vexs[$j];
if($final[$temp] != 1 && $weight[$temp] < $min){
$key = $temp;
$min = $weight[$temp];
}
}
$final[$key] = 1;
for($j = 0; $j < count($this->vexs); $j ++){
$temp = $this->vexs[$j];
if($final[$temp] != 1 && ($min + $this->arc[$key][$temp]) < $weight[$temp]){
$pre[$temp] = $key;
$weight[$temp] = $min + $this->arc[$key][$temp];
}
}
}
return $pre;
}
//kruscal算法
private function kruscal(){
$this->krus = array();
foreach($this->vexs as $value){
$krus[$value] = 0;
}
foreach($this->arc as $key=>$value){
$begin = $this->findroot($key);
foreach($value as $k=>$v){
$end = $this->findroot($k); 本文链接http://www.cxybl.com/html/wlbc/Php/20120607/28507.html应该大致熟悉了一些学习过程，也许我的过程和你的有些出路，但是不管怎么样是殊途同归，我写这么多，也只是给大家一个借鉴的机会，至于好与不好，默默不敢打包票^0^

作者: 分手快乐 时间: 2015-2-4 00:26
我还是推荐用firefox ，配上firebug 插件调试js能省下不受时间。谷歌的浏览器最好也不少用，因为谷歌的大侠们实在是太天才啦，把一些原来的js代码加了一些特效。

作者: 柔情似水 时间: 2015-2-5 15:12
为了以后维护的方便最好是代码上都加上注释，“予人方便，自己方便”。此外开发文档什么的最好都弄齐全。我觉得这是程序员必备的素质。虽然会消耗点很多的时间。但是确实是非常有必要的。

作者: 爱飞 时间: 2015-2-12 10:44
这些都是最基本最常用功能，我们这些菜鸟在系统学习后，可以先对这些功能深入研究。

作者: 老尸 时间: 2015-2-20 01:32
这些中手常用的知识，当你把我说的这些关键字都可以熟练运用的时候，你可以选择自己

作者: 简单生活 时间: 2015-2-21 00:26
个人呢觉得，配wamp 最容易漏的一步就是忘了把$PHP$目录下的libmysql.dll拷贝到windows系统目录的system32目录下，还有重启apache。

作者: 第二个灵魂 时间: 2015-2-28 23:50
曾经犯过一个很低级的错误，我在文件命名的时候用了一个横线\\\\\\\'-\\\\\\\' 号，结果找了好几个小时的错误，事实是命名的时候是不能用横线 \\\\\\\'-\\\\\\\' 的，应该用的是下划线 \\\\\\\'_\\\\\\\' ;

作者: 只想知道 时间: 2015-3-10 10:51
Apache不是非得用80或者8080端口的，我刚开始安得时候就是80端口老占用，就用了个 81端口，结果照常，就是输localhost的时候，应该输入为 localhost:81

作者: 小妖女 时间: 2015-3-17 06:11
当留言板完成的时候，下步可以把做1个单人的blog程序，做为目标，

作者: 谁可相欹 时间: 2015-3-23 22:46
首先我是坚决反对新手上来就用框架的，因为对底层的东西一点都不了解，造成知识上的真空，会对以后的发展不利。我的观点上手了解下框架就好，代码还是手写。当然啦如果是位别的编程语言的高手的话，这个就另当别论啦。

作者: 山那边是海 时间: 2015-3-26 22:31
这些中手常用的知识，当你把我说的这些关键字都可以熟练运用的时候，你可以选择自己

作者: 灵魂腐蚀 时间: 2015-4-1 10:20
本文当是我的笔记啦，遇到的问题随时填充

作者: 乐观 时间: 2015-4-12 21:04
我还是强烈建议自己搭建php环境。因为在搭建的过程中你会遇到一些问题，通过搜索或是看php手册解决问题后，你会更加深刻的理解它们的工作原理，了解到php配置文件中的一些选项设置。

作者: 仓酷云 时间: 2015-4-15 03:20
对于懒惰的朋友，我推荐php的集成环境xampp或者是wamp。这两个软件安装方便，使用简单。但是我还是强烈建议自己动手搭建开发环境。

作者: 若相依 时间: 2015-4-17 11:57
Ps：以上纯属原创，如有雷同，纯属巧合

作者: 飘飘悠悠 时间: 2015-4-20 00:18
实践是检验自己会不会的真理。

作者: 再现理想 时间: 2015-5-1 22:08
再就是混迹于论坛啦，咱们的phpchina的论坛就很强大，提出的问题一般都是有达人去解答的，以前的帖子也要多看看也能学到不少前辈们的经验。别的不错的论坛例如php100，javaeye也是很不错的。

作者: 金色的骷髅 时间: 2015-5-10 23:44
这些中手常用的知识，当你把我说的这些关键字都可以熟练运用的时候，你可以选择自己

作者: 兰色精灵 时间: 2015-6-6 16:14
Ps：以上纯属原创，如有雷同，纯属巧合

作者: 莫相离 时间: 2015-6-10 11:14
做为1门年轻的语言，php一直很努力。

作者: 愤怒的大鸟 时间: 2015-6-12 15:01
我学习了一段时间后，我发现效果并不好（估计是我自身的问题）。因为一个人的精力总是有限的，同时学习这么多，会导致每个的学习时间都得不到保证。

欢迎光临仓酷云 (http://ckuyun.com/)