PHP에서 너비 우선 검색 알고리즘을 구현하는 방법에 대한 자세한 소개

이 글에서는 주로 PHP에서의 너비우선탐색 알고리즘(BFS, Broad First Search)을 소개하고, 너비우선탐색 알고리즘의 원리를 간략하게 설명하고, PHP에서 너비우선탐색 알고리즘을 구현하는 단계와 관련 연산 기술을 분석합니다. 구체적인 예가 포함된 PHP가 필요합니다. 친구들은 이 기사를 참조할 수 있습니다.

이 기사에서는 PHP에서 너비 우선 검색 알고리즘을 구현하는 방법을 설명합니다. 다음과 같이 참고할 수 있도록 모든 사람과 공유하세요.

너비 우선 검색의 알고리즘 아이디어 Breadth-FirstTraversal

Breadth-First Traversal은 연결된 그래프에 대한 순회 전략입니다. 그 아이디어는 정점 V0에서 시작하여 먼저 정점 주변의 더 넓은 영역을 방사형으로 횡단하는 것이므로 이름이 붙여졌습니다.

너비 우선 검색 순회는 트리의 계층 순회와 유사합니다. 방향이 없는 연결 그래프의 경우, 너비 우선 탐색은 그래프의 특정 정점 v0부터 시작하여 v0의 방문하지 않은 인접 점 w1, w2,...을 차례로 검색합니다. 그런 다음 w1의 방문하지 않은 각 인접 지점, w2의 방문하지 않은 각 인접 지점을 순차적으로 검색합니다. 즉, v0부터 시작해서 가까운 곳부터 먼 곳까지, 연결된 그래프의 모든 꼭지점을 한 번 방문할 때까지 v0에 연결되어 있고 경로 길이가 1, 2,...인 정점을 레벨별로 방문합니다.

각 레이어의 정점에 특정 순서로 액세스하면 프로그램 구현에 편리합니다. 너비 우선 검색의 전체 계층 순서는 확실하며 각 레이어의 액세스 순서는 고유하지 않습니다.

구체적인 설명은 다음과 같습니다.

그래프 G의 초기 상태가 모든 정점을 방문하지 않았고 G의 정점 i가 초기점으로 선택되었다고 가정하면 너비에 대한 기본 개념이 설정됩니다. -첫 번째 검색은 다음과 같습니다.

(1) 그래프의 특정 정점 V를 방문하여 기록합니다.
(2) V의 모든 인접 정점을 순차적으로 방문합니다.
(3) 이러한 인접 점부터 시작하여 그래프에서 방문한 모든 정점의 인접 점을 방문할 때까지 방문하지 않은 인접 점을 차례로 방문합니다.
(4) (3)단계.

그리고 그래프의 모든 정점을 방문할 때까지 계속됩니다.

폭 우선 검색은 레이어를 검색하고 액세스할 때 방문한 정점을 기억해야 합니다. 그래야 하위 수준 정점에 액세스할 때 방문한 정점부터 시작하여 인접 지점을 검색하고 액세스할 수 있습니다. 따라서 너비 우선 탐색에서는 방문한 정점이 대기열의 끝부터 순차적으로 대기열에 들어가도록 대기열을 설정해야 합니다. 하위 정점을 검색하고 접근할 때에는 먼저 팀장이 방문한 상위 정점을 꺼내고, 이 정점부터 시작하여 인접한 지점을 검색하고 접근한다.

SearchInterface.php:

<?php
abstract class SearchInterface
{
  protected $G;//图
  protected $s;//图的首节点
  function __construct($_G,$_s){$this->G = $_G;$this->s = $_s;}
  public abstract function search();
}
?>

bfs.php:

<?php
include_once(&#39;SearchInterface.php&#39;);
class bfs extends SearchInterface
{
  private $d = array();//源点s和顶点u之间的距离
  private $tt = array();//结点u的父母存于变量
  private $visit = array();//已访问节点
  function __construct($_G,$_s)
  {
    parent::__construct($_G,$_s);
    //初始化$d/$tt,初始值为无穷大/NULL
    for($i=0;$i<9;$i++)
    {
      $this->d[$i] = 20000;
      $this->tt[$i] = NULL;
      $this->visit[$i] = 0;
    }
  }
  public function search()
  {
    //访问所有节点
    $queue = array();
    for($i=0;$i<9;$i++)
    {
      if($this->visit[$i]==0)
      {
        array_push($queue,$i);
        while(!empty($queue))
        {
          $_s = array_shift($queue);
          $this->visit[$_s] = 1;
          echo ($_s+1).&#39;<br>&#39;;
          $link_s = $this->G->get_links($_s);
          //获取和s直接相连的顶点u
          foreach($link_s as $j => $u)
          {
            if($this->visit[$u]==0)
            {
              array_push($queue,$u);
              $this->visit[$u] = 2;
            }
          }
        }
      }
    }
  }
}
?>

사용법:

$G = new Graphic;
$search = new bfs($G,1);
$search->search();

위 내용은 PHP에서 너비 우선 검색 알고리즘을 구현하는 방법에 대한 자세한 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!