너비우선탐색 알고리즘이란?

폭 우선 탐색 알고리즘은 [폭 우선 탐색] 또는 [수평 우선 탐색]이라고도 하며, BFS라고도 합니다. 그래프 검색 알고리즘입니다(문제의 상관관계를 표현하기 위해 그래프를 사용하는 기능 필요). BFS는 가장 간단한 그래프 검색 알고리즘 중 하나이며 많은 중요한 그래프 검색 알고리즘의 프로토타입이기도 합니다.

폭우선탐색 알고리즘이 무엇인가요? PHP를 사용하여 구현하는 방법은 무엇입니까? 다음 글에서 소개하겠습니다. 도움이 필요한 친구들이 모두 참고할 수 있기를 바랍니다.

Breadth-FirstTraversal

Breadth-First Search 알고리즘(너비 우선 검색), BFS라고도 하며 "너비 우선 검색"이라고도 함 BFS는 그래프 검색에 사용됩니다. 알고리즘(문제의 상관관계를 나타내기 위해 그래프를 사용할 수 있어야 함)

BFS는 가장 간단한 그래프 검색 알고리즘 중 하나입니다. 이 알고리즘은 또한 많은 중요한 그래프 알고리즘의 프로토타입이기도 합니다.

BFS는 경험 법칙 알고리즘을 사용하지 않습니다. 알고리즘 관점에서 노드 확장으로 인한 모든 하위 노드는 선입 선출 대기열에 추가됩니다. 일반적인 실험에서는 이웃 노드가 테스트되지 않은 노드는 open(예: 큐 또는 연결 목록)이라는 컨테이너에 배치되고, 테스트된 노드는 닫힌 중간이라는 컨테이너에 배치됩니다.

PHP에서 너비 우선 검색 알고리즘을 구현하는 방법은 무엇입니까?

폭 우선 검색의 알고리즘 아이디어

폭 우선 순회는 연결된 그래프의 순회 전략입니다. 그 아이디어는 정점 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;
            }
          }
        }
      }
    }
  }
}
?>

Usage:

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

더 많은 관련 지식을 보려면 PHP 중국어 웹사이트를 방문하세요! !

위 내용은 너비우선탐색 알고리즘이란?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!