当前位置:Gxlcms > PHP教程 > 详解PHP实现深度优先搜索算法

详解PHP实现深度优先搜索算法

时间:2021-07-01 10:21:17 帮助过:4人阅读

这篇文章主要介绍了PHP实现深度优先搜索算法(DFS,Depth First Search),简单分析了深度优先搜索算法的原理并结合具体实例给出了php实现深度优先搜索的具体步骤与相关操作技巧,需要的朋友可以参考下

本文实例讲述了PHP实现深度优先搜索算法。分享给大家供大家参考,具体如下:

深度优先搜索的实现原理:

实现代码:


  1. <?php
  2. class Search_Method
  3. {
  4. //无向图的数组描述
  5. private $dfs_save;
  6. //全局记录数组
  7. private $arr;
  8. //控制分支-
  9. private $k = 0;
  10. public function __construct()
  11. {
  12. $this->dfs_save = array(
  13. array(0,1,1,1,0,0,0,0,0),
  14. array(1,0,0,0,1,0,0,0,0),
  15. array(1,0,0,0,0,1,0,0,0),
  16. array(1,0,0,0,0,0,1,0,0),
  17. array(0,1,0,0,0,1,0,0,1),
  18. array(0,0,1,0,1,0,0,1,0),
  19. array(0,0,0,1,0,0,0,0,0),
  20. array(0,0,0,0,0,1,0,0,0),
  21. array(0,0,0,0,1,0,0,0,0),
  22. );
  23. $this->arr = array();
  24. }
  25. //深度优先搜索的递归实现方法
  26. public function dfs($v)
  27. {
  28. //对顶点做一些操作
  29. echo str_repeat("-",$this->k);
  30. echo 'V'.($v+1).'<br>';
  31. //记录已访问的顶点
  32. $this->arr[]= $v;
  33. //查找与顶点相连接的顶点,如果存在就继续深度优先搜索
  34. for($i=0;$i<9;$i++)
  35. {
  36. if(!in_array($i,$this->arr)&&$this->dfs_save[$v][$i]==1)
  37. {
  38. $this->k++;
  39. $this->dfs($i);
  40. }
  41. }
  42. $this->k--;
  43. return;
  44. }
  45. }
  46. ?>

实现输出结果:


  1. V1
  2. -V2
  3. --V5
  4. ---V6
  5. ----V3
  6. ----V8
  7. ---V9
  8. -V4
  9. --V7

以上就是详解PHP实现深度优先搜索算法的详细内容,更多请关注Gxl网其它相关文章!

人气教程排行