PHP教程之PHP完成图的邻矩阵及普利姆算法(Prim)

完成一个功能齐全的动态站点  

1. <?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[0];                 $last = $strArr[1];                                   $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]=>0);                          for($i = 1; $i < count($this->vexs); $i ++){                 $this->primArc[$this->vexs[$i]] = $this->arc[$this->vexs[0]][$this->vexs[$i]];                 $this->primVexs[$this->vexs[$i]] = $this->vexs[0];             }              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[0]);             $this->primArc = array();              next($this->arc[key($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[key($current)] = 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。这两个软件安装方便，使用简单。但是我还是强烈建议自己动手搭建开发环境。