>  기사  >  백엔드 개발  >  PHP에서 구현된 깊이 우선 탐색 알고리즘에 대한 자세한 설명

PHP에서 구현된 깊이 우선 탐색 알고리즘에 대한 자세한 설명

巴扎黑
巴扎黑원래의
2017-09-18 09:58:591900검색

이 글에서는 주로 PHP에서 구현되는 깊이 우선 탐색 알고리즘(DFS, Depth First Search)을 소개합니다. 깊이 우선 탐색 알고리즘의 원리를 간략하게 분석하고 구체적인 예를 결합하여 깊이 구현을 위한 구체적인 단계와 관련 운영 기법을 제공합니다. -PHP에서 우선 검색이 필요한 친구들이 참고할 수 있습니다

이 글에서는 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 &#39;V&#39;.($v+1).&#39;<br>&#39;;
    //记录已访问的顶点
    $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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.