论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2011-11-06 20:50 |只看该作者 |倒序浏览

PHP实现克鲁斯卡尔(kruscal)算法

Php代码

1.<?php
2. require 'edge.php';
3. $a = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i');
4. $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');
5.
6. $test = new Edge($a, $b);
7. print_r($test->kruscal());
8.?>
<?php
require '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());
?>

复制代码

Php代码

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