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

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[$key] as $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[$value] as $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[$key] as $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
， 算法
， 矩阵
， prims算法
， prim
Prim算法
普利姆算法、prim算法、最小生成树prim算法、prim算法求最小生成树、prim算法的时间复杂度，以便于您获取更多的相关知识。