本文實例展示了PHP實現的格魯斯卡爾算法（kruscal）的實現方法，分享給大家供大家參考。相信對于大家的PHP程序設計有一定的借鑒價值。
具體代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
<?phprequire 'edge.php';$a = array( 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i');$b = array( 'ab' => '10', 'af' => '11', 'gb' => '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');$test = new Edge($a, $b);print_r($test->kruscal());?> |
edge.php文件代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
<?php//邊集數組的邊類class EdgeArc { private $begin; //起始點 private $end; //結束點 private $weight; //權值 public function EdgeArc($begin, $end, $weight) { $this->begin = $begin; $this->end = $end; $this->weight = $weight; } public function getBegin() { return $this->begin; } public function getEnd() { return $this->end; } public function getWeight() { return $this->weight; }}class Edge { //邊集數組實現圖 private $vexs; //頂點集合 private $arc; //邊集合 private $arcData; //要構建圖的邊信息 private $krus; //kruscal算法時存放森林信息 public function Edge($vexsData, $arcData) { $this->vexs = $vexsData; $this->arcData = $arcData; $this->createArc(); } //創建邊 private function createArc() { foreach ($this->arcData as $key => $value) { $key = str_split($key); $this->arc[] = new EdgeArc($key[0], $key[1], $value); } } //對邊數組按權值排序 public function sortArc() { $this->quicklySort(0, count($this->arc) - 1, $this->arc); return $this->arc; } //采用快排 private function quicklySort($begin, $end, &$item) { if ($begin < 0($begin >= $end)) return; $key = $this->excuteSort($begin, $end, $item); $this->quicklySort(0, $key - 1, $item); $this->quicklySort($key + 1, $end, $item); } private function excuteSort($begin, $end, &$item) { $key = $item[$begin]; $left = array(); $right = array(); for ($i = ($begin + 1); $i <= $end; $i++) { if ($item[$i]->getWeight() <= $key->getWeight()) { $left[] = $item[$i]; } else { $right[] = $item[$i]; } } $return = $this->unio($left, $right, $key); $k = 0; for ($i = $begin; $i <= $end; $i++) { $item[$i] = $return[$k]; $k++; } return $begin + count($left); } private function unio($left, $right, $key) { return array_merge($left, array( $key ) , $right); } //kruscal算法 public function kruscal() { $this->krus = array(); $this->sortArc(); foreach ($this->vexs as $value) { $this->krus[$value] = "0"; } foreach ($this->arc as $key => $value) { $begin = $this->findRoot($value->getBegin()); $end = $this->findRoot($value->getEnd()); if ($begin != $end) { $this->krus[$begin] = $end; echo $value->getBegin() . "-" . $value->getEnd() . ":" . $value->getWeight() . "\n"; } } } //查找子樹的尾結點 private function findRoot($node) { while ($this->krus[$node] != "0") { $node = $this->krus[$node]; } return $node; }}?> |
感興趣的讀者可以調試運行一下本文克魯斯卡爾算法實例，相信會有新的收獲。
