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[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);       }    } ?>

复制代码