这篇文章主要介绍了PHP实现图的邻接矩阵表示及几种简单遍历算法,结合实例形式分析了php基于邻接矩阵实现图的定义及相关遍历操作技巧,需要的朋友可以参考下

本文实例讲述了PHP实现图的邻接矩阵表示及几种简单遍历算法，分享给大家供大家参考，具体如下：

在web开发中图这种数据结构的应用比树要少很多,但在一些业务中也常有出现,下面介绍几种图的寻径算法,并用PHP加以实现.

佛洛依德算法,主要是在顶点集内,按点与点相邻边的权重做遍历,如果两点不相连则权重无穷大,这样通过多次遍历可以得到点到点的最短路径,逻辑上最好理解,实现也较为简单,时间复杂度为O(n^3);

迪杰斯特拉算法,OSPF中实现最短路由所用到的经典算法,djisktra算法的本质是贪心算法,不断的遍历扩充顶点路径集合S,一旦发现更短的点到点路径就替换S中原有的最短路径,完成所有遍历后S便是所有顶点的最短路径集合了.迪杰斯特拉算法的时间复杂度为O(n^2);

克鲁斯卡尔算法,在图内构造最小生成树,达到图中所有顶点联通.从而得到最短路径.时间复杂度为O(N*logN);

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

运行结果：

1. Array
2. (
3. [vexs] => Array
4. (
5. [0] => a
6. [1] => b
7. [2] => f
8. [3] => i
9. [4] => c
10. [5] => g
11. [6] => h
12. [7] => e
13. [8] => d
14. )
15. [arc] => Array
16. (
17. [ab] => 10
18. [af] => 11
19. [bi] => 12
20. [ic] => 8
21. [bg] => 16
22. [gh] => 19
23. [he] => 7
24. [hd] => 16
25. )
26. )