- 论坛徽章:
- 0
|
|
PHP实现图的邻接矩阵
Php代码- 1.<?php
- 2. //调用
- 3. require 'mGraph.php';
- 4. $a = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j');
- 5. $b = array('ab', 'bc', 'be', 'cd', 'df', 'fg', 'gh', 'ga', 'hj', 'gi');
- 6.
- 7. $test = new MGraph($a, $b);
- 8. print_r($test->bfs());
- 9.?>
- <?php
- //调用
- require 'mGraph.php';
- $a = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j');
- $b = array('ab', 'bc', 'be', 'cd', 'df', 'fg', 'gh', 'ga', 'hj', 'gi');
-
- $test = new MGraph($a, $b);
- print_r($test->bfs());
- ?>
Php代码- 1.<?php
- 2. /**
- 3. * PHP 实现图邻接矩阵
- 4. *
- 5. * @author zhaojiangwei
- 6. * @since 2011/10/31 17:23
- 7. */
- 8.
- 9. class MGraph{
- 10. private $vexs; //顶点数组
- 11. private $arc; //边邻接矩阵,即二维数组
- 12. private $arcData; //边的数组信息
- 13. private $direct; //图的类型(无向或有向)
- 14. private $hasList; //尝试遍历时存储遍历过的结点
- 15. private $queue; //广度优先遍历时存储孩子结点的队列,用数组模仿
- 16. //private $infinity = 65535;//代表无穷,即两点无连接,建带权值的图时用,本示例不带权值
- 17.
- 18. public function MGraph($vexs, $arc, $direct = 0){
- 19. $this->vexs = $vexs;
- 20. $this->arcData = $arc;
- 21. $this->direct = $direct;
- 22. $this->initalizeArc();
- 23. $this->createArc();
- 24. }
- 25.
- 26. private function initalizeArc(){
- 27. foreach($this->vexs as $value){
- 28. foreach($this->vexs as $cValue){
- 29. $this->arc[$value][$cValue] = 0;
- 30. }
- 31. }
- 32. }
- 33.
- 34. //创建图 $direct:0表示无向图,1表示有向图
- 35. private function createArc(){
- 36. foreach($this->arcData as $key=>$value){
- 37. $strArr = str_split($value);
- 38. $first = $strArr[0];
- 39. $last = $strArr[1];
- 40.
- 41. $this->arc[$first][$last] = 1;
- 42. if(!$this->direct){
- 43. $this->arc[$last][$first] = 1;
- 44. }
- 45. }
- 46. }
- 47.
- 48. //一般遍历
- 49. public function reserve(){
- 50. $this->hasList = array();
- 51.
- 52. foreach($this->arc as $key=>$value){
- 53. if(!in_array($key, $this->hasList)){
- 54. $this->hasList[] = $key;
- 55. }
- 56.
- 57. foreach($value as $k=>$v){
- 58. if($v == 1 && !in_array($k, $this->hasList)){
- 59. $this->hasList[] = $k;
- 60. }
- 61. }
- 62. }
- 63.
- 64. foreach($this->vexs as $v){
- 65. if(!in_array($v, $this->hasList))
- 66. $this->hasList[] = $v;
- 67. }
- 68.
- 69. return implode($this->hasList);
- 70. }
- 71.
- 72. //广度优先遍历
- 73. public function bfs(){
- 74. $this->hasList = array();
- 75. $this->queue = array();
- 76.
- 77. foreach($this->arc as $key=>$value){
- 78. if(!in_array($key, $this->hasList)){
- 79. $this->hasList[] = $key;
- 80. $this->queue[] = $value;
- 81.
- 82. while(!emptyempty($this->queue)){
- 83. $child = array_shift($this->queue);
- 84.
- 85. foreach($child as $k=>$v){
- 86. if($v == 1 && !in_array($k, $this->hasList)){
- 87. $this->hasList[] = $k;
- 88. $this->queue[] = $this->arc[$k];
- 89. }
- 90. }
- 91. }
- 92. }
- 93. }
- 94.
- 95. return implode($this->hasList);
- 96.
- 97. }
- 98.
- 99. //执行深度优先遍历
- 100. public function excuteDfs($key){
- 101. $this->hasList[] = $key;
- 102.
- 103. foreach($this->arc[$key] as $k=>$v){
- 104. if($v == 1 && !in_array($k, $this->hasList))
- 105. $this->excuteDfs($k);
- 106. }
- 107. }
- 108.
- 109. //深度优先遍历
- 110. public function dfs(){
- 111. $this->hasList = array();
- 112.
- 113. foreach($this->vexs as $key){
- 114. if(!in_array($key, $this->hasList))
- 115. $this->excuteDfs($key);
- 116. }
- 117.
- 118. return implode($this->hasList);
- 119. }
- 120.
- 121. //返回图的二维数组表示
- 122. public function getArc(){
- 123. return $this->arc;
- 124. }
- 125.
- 126. //返回结点个数
- 127. public function getVexCount(){
- 128. return count($this->vexs);
- 129. }
- 130. }
- 131.
- 132.?>
|
|
免费注册
发表于 2011-11-02 20:48
