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;$ivexs);$i++){
for($k=0;$kvexs);$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;$ivexs);$i++){
$key=0;
$min=$this->infinity;
for($j=1;$jvexs);$j++){
$temp=$this->vexs[$j];
if($final[$temp]!=1&&$weight[$temp]<$min){
$key=$temp;
$min=$weight[$temp];
}
}
$final[$key]=1;
for($j=0;$jvexs);$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;$ivexs);$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;$ivexs);$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程序设计有所帮助。