PHP实现图的邻接矩阵表示及几种简单遍历算法分析
本文实例讲述了PHP实现图的邻接矩阵表示及几种简单遍历算法。分享给大家供大家参考,具体如下:
在web开发中图这种数据结构的应用比树要少很多,但在一些业务中也常有出现,下面介绍几种图的寻径算法,并用PHP加以实现.
佛洛依德算法,主要是在顶点集内,按点与点相邻边的权重做遍历,如果两点不相连则权重无穷大,这样通过多次遍历可以得到点到点的最短路径,逻辑上最好理解,实现也较为简单,时间复杂度为O(n^3);
迪杰斯特拉算法,OSPF中实现最短路由所用到的经典算法,djisktra算法的本质是贪心算法,不断的遍历扩充顶点路径集合S,一旦发现更短的点到点路径就替换S中原有的最短路径,完成所有遍历后S便是所有顶点的最短路径集合了.迪杰斯特拉算法的时间复杂度为O(n^2);
克鲁斯卡尔算法,在图内构造最小生成树,达到图中所有顶点联通.从而得到最短路径.时间复杂度为O(N*logN);
vexs=$vexs; $this->arcData=$arc; $this->direct=$direct; $this->initalizeArc(); $this->createArc(); } privatefunctioninitalizeArc(){ foreach($this->vexsas$value){ foreach($this->vexsas$cValue){ $this->arc[$value][$cValue]=($value==$cValue?0:$this->infinity); } } } //创建图$direct:0表示无向图,1表示有向图 privatefunctioncreateArc(){ foreach($this->arcDataas$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算法 publicfunctionfloyd(){ $path=array();//路径数组 $distance=array();//距离数组 foreach($this->arcas$key=>$value){ foreach($valueas$k=>$v){ $path[$key][$k]=$k; $distance[$key][$k]=$v; } } for($j=0;$jvexs);$j++){ for($i=0;$i vexs);$i++){ for($k=0;$k 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]]; } } } } returnarray($path,$distance); } //djikstra算法 publicfunctiondijkstra(){ $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 vexs);$i++){ $key=0; $min=$this->infinity; for($j=1;$j 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 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算法 privatefunctionkruscal(){ $this->krus=array(); foreach($this->vexsas$value){ $krus[$value]=0; } foreach($this->arcas$key=>$value){ $begin=$this->findRoot($key); foreach($valueas$k=>$v){ $end=$this->findRoot($k); if($begin!=$end){ $this->krus[$begin]=$end; } } } } //查找子树的尾结点 privatefunctionfindRoot($node){ while($this->krus[$node]>0){ $node=$this->krus[$node]; } return$node; } //prim算法,生成最小生成树 publicfunctionprim(){ $this->primVexs=array(); $this->primArc=array($this->vexs[0]=>0); for($i=1;$i 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 vexs);$i++){ $min=$this->infinity; $key; foreach($this->vexsas$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; } //一般算法,生成最小生成树 publicfunctionbst(){ $this->primVexs=array($this->vexs[0]); $this->primArc=array(); next($this->arc[key($this->arc)]); $key=NULL; $current=NULL; while(count($this->primVexs) vexs)){ foreach($this->primVexsas$value){ foreach($this->arc[$value]as$k=>$v){ if(!in_array($k,$this->primVexs)&&$v!=0&&$v!=$this->infinity){ if($key==NULL||$v $v); } } } } $this->primVexs[]=$key; $this->primArc[key($current)]=current($current); $key=NULL; $current=NULL; } returnarray('vexs'=>$this->primVexs,'arc'=>$this->primArc); } //一般遍历 publicfunctionreserve(){ $this->hasList=array(); foreach($this->arcas$key=>$value){ if(!in_array($key,$this->hasList)){ $this->hasList[]=$key; } foreach($valueas$k=>$v){ if($v==1&&!in_array($k,$this->hasList)){ $this->hasList[]=$k; } } } foreach($this->vexsas$v){ if(!in_array($v,$this->hasList)) $this->hasList[]=$v; } returnimplode($this->hasList); } //广度优先遍历 publicfunctionbfs(){ $this->hasList=array(); $this->queue=array(); foreach($this->arcas$key=>$value){ if(!in_array($key,$this->hasList)){ $this->hasList[]=$key; $this->queue[]=$value; while(!empty($this->queue)){ $child=array_shift($this->queue); foreach($childas$k=>$v){ if($v==1&&!in_array($k,$this->hasList)){ $this->hasList[]=$k; $this->queue[]=$this->arc[$k]; } } } } } returnimplode($this->hasList); } //执行深度优先遍历 publicfunctionexcuteDfs($key){ $this->hasList[]=$key; foreach($this->arc[$key]as$k=>$v){ if($v==1&&!in_array($k,$this->hasList)) $this->excuteDfs($k); } } //深度优先遍历 publicfunctiondfs(){ $this->hasList=array(); foreach($this->vexsas$key){ if(!in_array($key,$this->hasList)) $this->excuteDfs($key); } returnimplode($this->hasList); } //返回图的二维数组表示 publicfunctiongetArc(){ return$this->arc; } //返回结点个数 publicfunctiongetVexCount(){ returncount($this->vexs); } } $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=newMGraph($a,$b); print_r($test->bst());
运行结果:
Array ( [vexs]=>Array ( [0]=>a [1]=>b [2]=>f [3]=>i [4]=>c [5]=>g [6]=>h [7]=>e [8]=>d ) [arc]=>Array ( [ab]=>10 [af]=>11 [bi]=>12 [ic]=>8 [bg]=>16 [gh]=>19 [he]=>7 [hd]=>16 ) )
更多关于PHP相关内容感兴趣的读者可查看本站专题:《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》
希望本文所述对大家PHP程序设计有所帮助。