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


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

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



实现代码：





<?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







更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《PHP基本语法入门教程》、《php面向对象程序设计入门教程》、《php字符串(string)用法总结》及《php程序设计算法总结》

希望本文所述对大家PHP程序设计有所帮助。