这篇文章主要介绍了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. )

Tags: PHP邻接矩阵 PHP遍历算法

分享到：