PHP教程之PHP完成图的邻矩阵及普利姆算法(Prim)
完成一个功能齐全的动态站点 <?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 class MGraph{ private $vexs; //极点数组 private $arc; //边邻接矩阵,即二维数组 private $arcData; //边的数组信息 private $direct; //图的类型(无向或有向) private $hasList; //测验考试
遍用时
存储遍历过的结点 private $queue; //广度优先遍用时
存储孩子结点的队列,用数组仿照
private $infinity = 65535;//代表无量
,即两点无毗连
,建带权值的图时用,本示例不带权值 private $primVexs; //prim算法时保留
极点
private $primArc; //prim算法时保留
边 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; } } } //prim算法,生成最小生成树 public function prim(){ $this->primVexs = array(); $this->primArc = array($this->vexs=>0); for($i = 1; $i < count($this->vexs); $i ++){ $this->primArc[$this->vexs[$i]] = $this->arc[$this->vexs][$this->vexs[$i]]; $this->primVexs[$this->vexs[$i]] = $this->vexs; } for($i = 0; $i < count($this->vexs); $i ++){ $min = $this->infinity; $key; foreach($this->vexs as $k=>$v){ if($this->primArc[$v] != 0 && $this->primArc[$v] < $min){ $key = $v; $min = $this->primArc[$v]; } } $this->primArc[$key] = 0; foreach($this->arc[$key] as $k=>$v){ if($this->primArc[$k] != 0 && $v < $this->primArc[$k]){ $this->primArc[$k] = $v; $this->primVexs[$k] = $key; } } } return $this->primVexs; } //普通
算法,生成最小生成树 public function bst(){ $this->primVexs = array($this->vexs); $this->primArc = array(); next($this->arc); $key = NULL; $current = NULL; while(count($this->primVexs) < count($this->vexs)){ foreach($this->primVexs as $value){ foreach($this->arc[$value] as $k=>$v){ if(!in_array($k, $this->primVexs) && $v != 0 && $v != $this->infinity){ if($key == NULL$v < current($current)){ $key = $k; $current = array($value . $k=>$v); } } } } $this->primVexs[] = $key; $this->primArc = current($current); $key = NULL; $current = NULL; } return array('vexs'=>$this->primVexs, 'arc'=>$this->primArc); } //普通
遍历 public function reserve(){ $this->hasList = array(); foreach($this->arc as $key=>$value){ if(!in_array($key, $this->hasList)){ $this->hasList[] = $key; } foreach($value as $k=>$v){ if($v == 1 && !in_array($k, $this->hasList)){ $this->hasList[] = $k; } } } foreach($this->vexs as $v){ if(!in_array($v, $this->hasList)) $this->hasList[] = $v; } return implode($this->hasList); } //广度优先遍历 public function bfs(){ $this->hasList = array(); $this->queue = array(); foreach($this->arc as $key=>$value){ if(!in_array($key, $this->hasList)){ $this->hasList[] = $key; $this->queue[] = $value; while(!emptyempty($this->queue)){ $child = array_shift($this->queue); foreach($child as $k=>$v){ if($v == 1 && !in_array($k, $this->hasList)){ $this->hasList[] = $k; $this->queue[] = $this->arc[$k]; } } } } } return implode($this->hasList); } //履行
深度优先遍历 public function excuteDfs($key){ $this->hasList[] = $key; foreach($this->arc[$key] as $k=>$v){ if($v == 1 && !in_array($k, $this->hasList)) $this->excuteDfs($k); } } //深度优先遍历 public function dfs(){ $this->hasList = array(); foreach($this->vexs as $key){ if(!in_array($key, $this->hasList)) $this->excuteDfs($key); } return implode($this->hasList); } //前往
图的二维数组暗示
public function getArc(){ return $this->arc; } //前往
结点个数 public function getVexCount(){ return count($this->vexs); } } ?> 我先解释一下我的学习思路。 爱上php，他也会爱上你。 遇到出错的时候，我经常把错误信息直接复制到 google的搜索栏，一般情况都是能搜到结果的，不过有时候会搜出来一大片英文的出来，这时候就得过滤一下，吧中文的弄出来，挨着式方法。 这些中手常用的知识，当你把我说的这些关键字都可以熟练运用的时候，你可以选择自己 php是动态网站开发的优秀语言，在学习的时候万万不能冒进。在系统的学习前，我认为不应该只是追求实现某种效果，因为即使你复制他人的代码调试成功，实现了你所期望的效果，你也不了解其中的原理。 实践是检验自己会不会的真理。 最后介绍一个代码出错，但是老找不到错误方法，就是 go to wc （囧），出去换换气没准回来就找到错误啦。 不禁又想起那些说php是草根语言的人，为什么认得差距这么大呢。 有时候汉字的空格也能导致页面出错，所以在写代码的时候，要输入空格最好用引文模式。 不禁又想起那些说php是草根语言的人，为什么认得差距这么大呢。 本人接触php时间不长，算是phper中的小菜鸟一只吧。由于刚开始学的时候没有名师指，碰过不少疙瘩，呗很多小问题卡过很久，白白浪费不少宝贵的时间，在次分享一些子的学习的心得。 再就是混迹于论坛啦，咱们的phpchina的论坛就很强大，提出的问题一般都是有达人去解答的，以前的帖子也要多看看也能学到不少前辈们的经验。别的不错的论坛例如php100，javaeye也是很不错的。 找到的的资料很多都是在论坛里的，需要注册，所以我一般没到一个论坛都注册一个id，所有的id都注册成一样的，这样下次再进来的时候就不用重复注册啦。当然有些论坛的某些资料是需要的付费的。 使用 jquery 等js框架的时候，要随时注意浏览器的更新情况，不然很容易发生框架不能使用。 建数据库表的时候，int型要输入长度的，其实是个摆设的输入几位都没影响的，只要大于4就行，囧。 对于懒惰的朋友，我推荐php的集成环境xampp或者是wamp。这两个软件安装方便，使用简单。但是我还是强烈建议自己动手搭建开发环境。 最后祝愿，php会给你带来快乐的同时 你也会给他带来快乐。 这些中手常用的知识，当你把我说的这些关键字都可以熟练运用的时候，你可以选择自己 对于懒惰的朋友，我推荐php的集成环境xampp或者是wamp。这两个软件安装方便，使用简单。但是我还是强烈建议自己动手搭建开发环境。
页:
[1]