• 欢迎访问搞代码网站,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站!
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏搞代码吧

PHP实现图的邻矩阵及普利姆算法(Prim)_php

php 搞代码 3年前 (2018-06-21) 73次浏览 已收录 0个评论
  1. <?php 
  2.     require 'mGraph.php'
  3.     $a = array('a''b''c''d''e''f''g''h''i'); 
  4.     $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');//键为边,值权值 
  5.       
  6.     $test = new MGraph($a$b); 
  7.     print_r($test->prim()); 
  8. ?> 
  9. //mGraph.php 
  10. <?php 
  11.     class MGraph{ 
  12.         private $vexs//顶点数组 
  13.         private $arc//边邻接矩阵,即二维数组        
  14.         private $arcData//边的数组信息 
  15.         private $direct//图的类型(无向或有向) 
  16.         private $hasList//尝试遍历时存储遍历过的结点 
  17.         private $queue//广度优先遍历时存储孩子结点的队列,用数组模仿 
  18.         private $infinity = 65535;//代表无穷,即两点无连接,建带权值的图时用,本示例不带权值  
  19.         private $primVexs//prim算法时保存顶点 
  20.         private $primArc//prim算法时保存边 
  21.          
  22.         public function MGraph($vexs$arc$direct = 0){ 
  23.             $this->vexs = $vexs
  24.             $this->arcData = $arc
  25.             $this->direct = $direct
  26.             $this->initalizeArc(); 
  27.             $this->createArc();  
  28.         } 
  29.  
  30.         private function initalizeArc(){ 
  31.             foreach($this->vexs as $value){ 
  32.                 foreach($this->vexs as $cValue){ 
  33.                     $this->arc[$value][$cValue] = ($value == $cValue ? 0 : $this->infinity); 
  34.                 } 
  35.             } 
  36.         } 
  37.  
  38.         //创建图 $direct:0表示无向图,1表示有向图 
  39.         private function createArc(){ 
  40.             foreach($this->arcData as $key=>$value){ 
  41.                 $strArr = str_split($key); 
  42.                 $first = $strArr[0]; 
  43.                 $last = $strArr[1]; 
  44.                   
  45.                 $this->arc[$first][$last] = $value
  46.                 if(!$this->direct){ 
  47.                     $this->arc[$last][$first] = $value;  
  48.                 } 
  49.             } 
  50.         } 
  51.  
  52.         //prim算法,生成最小生成树 
  53.         public function prim(){ 
  54.             $this->primVexs = array(); 
  55.             $this->primArc = array($this->vexs[0]=>0); 
  56.              
  57.             for($i = 1; $i < count($this->vexs); $i ++){ 
  58.                 $this->primArc[$this->vexs[$i]] = $this->arc[$this->vexs[0]][$this->vexs[$i]]; 
  59.                 $this->primVexs[$this->vexs[$i]] = $this->vexs[0]; 
  60.             } 
  61.  
  62.             for($i = 0; $i < count($this->vexs); $i ++){ 
  63.                 $min = $this->infinity; 
  64.                 $key
  65.  
  66.                 foreach($this->vexs as $k=>$v){ 
  67.                     if($this->primArc[$v] != 0 && $this->primArc[$v] < $min){ 
  68.                         $key = $v
  69.                         $min = $this->primArc[$v]; 
  70.                     } 
  71.                 } 
  72.  
  73.                 $this->primArc[$key] = 0; 
  74.  
  75.                 foreach($this->arc[$keyas $k=>$v){ 
  76.                     if($this->primArc[$k] != 0 && $v < $this->primArc[$k]){ 
  77.                         $this->primArc[$k] = $v;   
  78.                         $this->primVexs[$k] = $key;  
  79.                     } 
  80.                 } 
  81.             } 
  82.  
  83.             return $this->primVexs; 
  84.         } 
  85.  
  86.         //一般算法,生成最小生成树 
  87.         public function bst(){ 
  88.             $this->primVexs = array($this->vexs[0]); 
  89.             $this->primArc = array(); 
  90.  
  91.             next($this->arc[key($this->arc)]);  
  92.             $key = NULL; 
  93.             $current = NULL; 
  94.  
  95.             while(count($this->primVexs) < count($this->vexs)){ 
  96.                 foreach($this->primVexs as $value){ 
  97.                     foreach($this->arc[$valueas $k=>$v){ 
  98.                         if(!in_array($k$this->primVexs) && $v != 0 && $v != $this->infinity){ 
  99.                             if($key == NULL  $v < current($current)){ 
  100.                                 $key = $k
  101.                                 $current = array($value . $k=>$v); 
  102.                             } 
  103.                         } 
  104.  
  105.                     } 
  106.                 } 
  107.  
  108.                 $this->primVexs[] = $key
  109.                 $this->primArc[key($current)] = current($current); 
  110.                 $key = NULL; 
  111.                 $current = NULL; 
  112.             } 
  113.  
  114.             return array('vexs'=>$this->primVexs, 'arc'=>$this->primArc); 
  115.         } 
  116.  
  117.         //一般遍历 
  118.         public function reserve(){ 
  119.             $this->hasList = array(); 
  120.  
  121.             foreach($this->arc as $key=>$value){ 
  122.                 if(!in_array($key$this->hasList)){ 
  123.                     $this->hasList[] = $key
  124.                 } 
  125.  
  126.                 foreach($value as $k=>$v){ 
  127.                     if($v == 1 && !in_array($k$this->hasList)){ 
  128.                         $this->hasList[] = $k;    
  129.                     } 
  130.                 } 
  131.             } 
  132.  
  133.             foreach($this->vexs as $v){ 
  134.                 if(!in_array($v$this->hasList)) 
  135.                     $this->hasList[] = $v
  136.             } 
  137.  
  138.             return implode($this->hasList); 
  139.         } 
  140.  
  141.         //广度优先遍历 
  142.         public function bfs(){ 
  143.             $this->hasList = array(); 
  144.             $this->queue = array(); 
  145.              
  146.             foreach($this->arc as $key=>$value){ 
  147.                 if(!in_array($key$this->hasList)){ 
  148.                     $this->hasList[] = $key
  149.                     $this->queue[] = $value
  150.  
  151.                     while(!emptyempty($this->queue)){ 
  152.                         $child = array_shift($this->queue); 
  153.                          
  154.                         foreach($child as $k=>$v){ 
  155.                             if($v == 1 && !in_array($k$this->hasList)){ 
  156.                                 $this->hasList[] = $k
  157.                                 $this->queue[] = $this->arc[$k];    
  158.                             } 
  159.                         } 
  160.                     } 
  161.                 } 
  162.             } 
  163.  
  164.             return implode($this->hasList); 
  165.               
  166.         } 
  167.  
  168.         //执行深度优先遍历 
  169.         public function excuteDfs($key){ 
  170.             $this->hasList[] = $key;   
  171.  
  172.             foreach($this->arc[$keyas $k=>$v){ 
  173.                 if($v == 1 && !in_array($k$this->hasList)) 
  174.                     $this->excuteDfs($k);    
  175.             } 
  176.         } 
  177.  
  178.         //深度优先遍历 
  179.         public function dfs(){ 
  180.             $this->hasList = array(); 
  181.  
  182.             foreach($this->vexs as $key){ 
  183.                 if(!in_array($key$this->hasList))  
  184.                     $this->excuteDfs($key);  
  185.             } 
  186.  
  187.             return implode($this->hasList); 
  188.         } 
  189.         //返回图的二维数组表示 
  190.         public function getArc(){ 
  191.             return $this->arc; 
  192.         } 
  193.         //返回结点个数 
  194.         public function getVexCount(){ 
  195.             return count($this->vexs); 
  196.         } 
  197.     } 
  198. ?> 

欢迎大家阅读php实现图的邻矩阵及普利姆算法(Prim)_php》,跪求各位点评,若觉得好的话请收藏本文,by 搞代码


喜欢 (0)
[搞代码]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址