幅優先探索アルゴリズムとは

幅優先検索アルゴリズムは、[幅優先検索] または [水平優先検索] とも呼ばれ、BFS と呼ばれます。これはグラフの検索アルゴリズムです (グラフを使用して問題の相関関係を表す機能が必要です)。 BFS は最も単純なグラフ検索アルゴリズムの 1 つであり、多くの重要なグラフ検索アルゴリズムのプロトタイプでもあります。

幅優先探索アルゴリズムとは何ですか? PHPを使用して実装するにはどうすればよいですか? 以下の記事で紹介しています。困っている友人が参考になれば幸いです。

Breadth-FirstTraversal

Breadth-First Search アルゴリズム (Breadth-First Search)、「Breadth-First Search」または「Transversal-First Search」とも呼ばれ、BFS はグラフ検索に使用されます。アルゴリズム (グラフを使用して問題の相関関係を表現できる必要があります)。

BFS は最も単純なグラフ検索アルゴリズムの 1 つであり、多くの重要なグラフ アルゴリズムのプロトタイプでもあります。

BFS は経験則アルゴリズムを使用しません。アルゴリズムの観点からは、ノードを拡張した結果として生じるすべての子ノードは先入れ先出しキューに追加されます。一般的な実験では、隣接ノードがテストされていないノードはオープンと呼ばれるコンテナ (キューやリンク リストなど) に配置され、テスト済みのノードはクローズド ミドルと呼ばれるコンテナに配置されます。

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

Usage:

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

関連知識の詳細については、PHP 中国語 Web サイト をご覧ください。 ！

以上が幅優先探索アルゴリズムとはの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。