PHP实现深度优先搜索算法(DFS,Depth First Search)详解

更新:2017-10-25    编辑:凌蓝    来源:geguai    人气:加载中...    字号:|

标签:实现  搜索  详解  算法  search  深度  百度搜索

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

深度优先搜索实现原理:

PHP实现深度优先搜索算法(DFS,Depth First Search)详解

实现代码:

<?php class Search_Method { //无向图的数组描述 private $dfs_save; //全局记载数组 private $arr; //把持分支- private $k = 0; public function __construct() { $this->dfs_save = array( array(0,1,1,1,0,0,0,0,0), array(1,0,0,0,1,0,0,0,0), array(1,0,0,0,0,1,0,0,0), array(1,0,0,0,0,0,1,0,0), array(0,1,0,0,0,1,0,0,1), array(0,0,1,0,1,0,0,1,0), array(0,0,0,1,0,0,0,0,0), array(0,0,0,0,0,1,0,0,0), array(0,0,0,0,1,0,0,0,0), ); $this->arr = array(); } //深度优先搜索的递归实现法子 public function dfs($v) { //对顶点做一些操作 echo str_repeat("-",$this->k); echo 'V'.($v+1).'<br>'; //记载已造访的顶点 $this->arr[]= $v; //查找与顶点相连接的顶点,如果存在就持续深度优先搜索 for($i=0;$i<9;$i++) { if(!in_array($i,$this->arr)&&$this->dfs_save[$v][$i]==1) { $this->k++; $this->dfs($i); } } $this->k--; return; } } ?>

实现输出结果:

V1 -V2 --V5 ---V6 ----V3 ----V8 ---V9 -V4 --V7


评论列表(网友评论仅供网友表达个人看法,并不表明本站同意其观点或证实其描述)

站点导航

您可能在找这些