PHPで幅優先検索アルゴリズムを実装する方法の詳細な紹介

この記事では、主に PHP での幅優先検索アルゴリズム (BFS、Broad First Search) の実装を紹介し、幅優先検索アルゴリズムの原理を簡単に説明し、幅優先検索アルゴリズムを実装する手順と関連する操作スキルを分析します。具体的な例を含む PHP は必須です。お友達はこの記事を参照してください

この記事では、PHP での幅優先検索アルゴリズムの実装について説明します。以下のように、参考のためにみんなと共有してください:

幅優先検索のアルゴリズムのアイデア 幅優先トラバーサル

幅優先トラバーサルは、接続されたグラフのトラバーサル戦略です。そのアイデアは、頂点 V0 から開始して、最初にその周囲のより広い領域を放射状に横断することであるため、この名前が付けられています。

幅優先検索の走査は、ツリーの階層の走査に似ています。無向接続グラフの場合、幅優先検索はグラフの特定の頂点 v0 から開始され、v0 を訪問した後、v0 の未訪問の隣接点 w1、w2、... を順に検索します。次に、w1 の未訪問の隣接点、w2 の未訪問の隣接点、... を順に検索します。つまり、v0 から始めて、近くから遠くまで、接続されたグラフ内のすべての頂点が 1 回訪問されるまで、v0 に接続されたパスを持ち、パスの長さが 1、2、... である頂点を順番に訪問します。

各層の頂点が特定の順序でアクセスされる限り、幅優先探索の全体的な階層順序は確実であり、各層のアクセス順序は一意ではありません。

具体的な説明は次のとおりです:

グラフ G の初期状態がすべての頂点が訪問されておらず、G の任意の頂点 i が初期点として選択されていると仮定すると、幅の基本的な考え方は次のようになります。 -最初の検索は:

(1) From グラフ内の特定の頂点 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 中国語 Web サイトの他の関連記事を参照してください。