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;
$last = $strarr;
$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] as $k=>$v){
$final[$k] = 0;
$pre[$k] = $this->vexs;
$weight[$k] = $v;
}
$final[$this->vexs] = 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^ 我还是推荐用firefox ，配上firebug 插件调试js能省下不受时间。谷歌的浏览器最好也不少用，因为谷歌的大侠们实在是太天才啦，把一些原来的js代码加了一些特效。 为了以后维护的方便最好是代码上都加上注释，“予人方便，自己方便”。此外开发文档什么的最好都弄齐全。我觉得这是程序员必备的素质。虽然会消耗点很多的时间。但是确实是非常有必要的。 这些都是最基本最常用功能，我们这些菜鸟在系统学习后，可以先对这些功能深入研究。 这些中手常用的知识，当你把我说的这些关键字都可以熟练运用的时候，你可以选择自己 个人呢觉得，配wamp 最容易漏的一步就是忘了把$PHP$目录下的libmysql.dll拷贝到windows系统目录的system32目录下，还有重启apache。 曾经犯过一个很低级的错误，我在文件命名的时候用了一个横线\\\\\\\'-\\\\\\\' 号，结果找了好几个小时的错误，事实是命名的时候 是不能用横线 \\\\\\\'-\\\\\\\' 的，应该用的是下划线\\\\\\\'_\\\\\\\' ; Apache不是非得用80或者8080端口的，我刚开始安得时候就是80端口老占用，就用了个 81端口，结果照常，就是输localhost的时候，应该输入为 localhost:81 当留言板完成的时候，下步可以把做1个单人的blog程序，做为目标， 首先我是坚决反对新手上来就用框架的，因为对底层的东西一点都不了解，造成知识上的真空，会对以后的发展不利。我的观点上手了解下框架就好，代码还是手写。当然啦如果是位别的编程语言的高手的话，这个就另当别论啦。 这些中手常用的知识，当你把我说的这些关键字都可以熟练运用的时候，你可以选择自己 本文当是我的笔记啦，遇到的问题随时填充 我还是强烈建议自己搭建php环境。因为在搭建的过程中你会遇到一些问题，通过搜索或是看php手册解决问题后，你会更加深刻的理解它们的工作原理，了解到php配置文件中的一些选项设置。 对于懒惰的朋友，我推荐php的集成环境xampp或者是wamp。这两个软件安装方便，使用简单。但是我还是强烈建议自己动手搭建开发环境。 Ps：以上纯属原创，如有雷同，纯属巧合 实践是检验自己会不会的真理。 再就是混迹于论坛啦，咱们的phpchina的论坛就很强大，提出的问题一般都是有达人去解答的，以前的帖子也要多看看也能学到不少前辈们的经验。别的不错的论坛例如php100，javaeye也是很不错的。 这些中手常用的知识，当你把我说的这些关键字都可以熟练运用的时候，你可以选择自己 Ps：以上纯属原创，如有雷同，纯属巧合 做为1门年轻的语言，php一直很努力。
页:
[1]
2