这篇文章主要介绍了PHP实现克鲁斯卡尔算法实例解析,是PHP程序设计中一个比较经典的应用,需要的朋友可以参考下

本文实例展示了PHP实现的格鲁斯卡尔算法（kruscal）的实现方法，分享给大家供大家参考。相信对于大家的PHP程序设计有一定的借鉴价值。

具体代码如下：

1. <?php 
2. require 'edge.php'; 
3. $a = array( 
4.   'a', 
5.   'b', 
6.   'c', 
7.   'd', 
8.   'e', 
9.   'f', 
10.   'g', 
11.   'h', 
12.   'i' 
13. ); 
14. $b = array( 
15.   'ab' => '10', 
16.   'af' => '11', 
17.   'gb' => '16', 
18.   'fg' => '17', 
19.   'bc' => '18', 
20.   'bi' => '12', 
21.   'ci' => '8', 
22.   'cd' => '22', 
23.   'di' => '21', 
24.   'dg' => '24', 
25.   'gh' => '19', 
26.   'dh' => '16', 
27.   'de' => '20', 
28.   'eh' => '7', 
29.   'fe' => '26' 
30. ); 
31. $test = new Edge($a, $b); 
32. print_r($test->kruscal()); 
33. ?> 

edge.php文件代码如下：

1. <?php 
2. //边集数组的边类 
3. class EdgeArc { 
4.   private $begin; //起始点 
5.   private $end; //结束点 
6.   private $weight; //权值 
7.   public function EdgeArc($begin, $end, $weight) { 
8.     $this->begin = $begin; 
9.     $this->end = $end; 
10.     $this->weight = $weight; 
11.   } 
12.   public function getBegin() { 
13.     return $this->begin; 
14.   } 
15.   public function getEnd() { 
16.     return $this->end; 
17.   } 
18.   public function getWeight() { 
19.     return $this->weight; 
20.   } 
21. } 
22. class Edge { 
23.   //边集数组实现图 
24.   private $vexs; //顶点集合 
25.   private $arc; //边集合 
26.   private $arcData; //要构建图的边信息 
27.   private $krus; //kruscal算法时存放森林信息 
28.   public function Edge($vexsData, $arcData) { 
29.     $this->vexs = $vexsData; 
30.     $this->arcData = $arcData; 
31.     $this->createArc(); 
32.   } 
33.   //创建边 
34.   private function createArc() { 
35.     foreach ($this->arcData as $key => $value) { 
36.       $key = str_split($key); 
37.       $this->arc[] = new EdgeArc($key[0], $key[1], $value); 
38.     } 
39.   } 
40.   //对边数组按权值排序 
41.   public function sortArc() { 
42.     $this->quicklySort(0, count($this->arc) - 1, $this->arc); 
43.     return $this->arc; 
44.   } 
45.   //采用快排 
46.   private function quicklySort($begin, $end, &$item) { 
47.     if ($begin < 0($begin >= $end)) return; 
48.     $key = $this->excuteSort($begin, $end, $item); 
49.     $this->quicklySort(0, $key - 1, $item); 
50.     $this->quicklySort($key + 1, $end, $item); 
51.   } 
52.   private function excuteSort($begin, $end, &$item) { 
53.     $key = $item[$begin]; 
54.     $left = array(); 
55.     $right = array(); 
56.     for ($i = ($begin + 1); $i <= $end; $i++) { 
57.       if ($item[$i]->getWeight() <= $key->getWeight()) { 
58.         $left[] = $item[$i]; 
59.       } else { 
60.         $right[] = $item[$i]; 
61.       } 
62.     } 
63.     $return = $this->unio($left, $right, $key); 
64.     $k = 0; 
65.     for ($i = $begin; $i <= $end; $i++) { 
66.       $item[$i] = $return[$k]; 
67.       $k++; 
68.     } 
69.     return $begin + count($left); 
70.   } 
71.   private function unio($left, $right, $key) { 
72.     return array_merge($left, array( 
73.       $key 
74.     ) , $right); 
75.   } 
76.   //kruscal算法 
77.   public function kruscal() { 
78.     $this->krus = array(); 
79.     $this->sortArc(); 
80.     foreach ($this->vexs as $value) { 
81.       $this->krus[$value] = "0"; 
82.     } 
83.     foreach ($this->arc as $key => $value) { 
84.       $begin = $this->findRoot($value->getBegin()); 
85.       $end = $this->findRoot($value->getEnd()); 
86.       if ($begin != $end) { 
87.         $this->krus[$begin] = $end; 
88.         echo $value->getBegin() . "-" . $value->getEnd() . ":" . $value->getWeight() . "\n"; 
89.       } 
90.     } 
91.   } 
92.   //查找子树的尾结点 
93.   private function findRoot($node) { 
94.     while ($this->krus[$node] != "0") { 
95.       $node = $this->krus[$node]; 
96.     } 
97.     return $node; 
98.   } 
99. } 
100. ?>  

感兴趣的读者可以调试运行一下本文克鲁斯卡尔算法实例，相信会有新的收获。

Tags: PHP鲁斯卡尔算法

分享到：