Detaillierte Einführung in die Methode zur Implementierung des Breitensuchalgorithmus in PHP

In diesem Artikel wird hauptsächlich die Implementierung des Breitensuchalgorithmus (BFS, Broad First Search) in PHP vorgestellt. Er beschreibt kurz das Prinzip des Breitensuchalgorithmus und analysiert die Schritte und zugehörigen Betriebstechniken zur Implementierung der Breitensuche Algorithmus in PHP mit konkreten Beispielen, Freunde in Not können sich auf

beziehen. Dieser Artikel beschreibt die Implementierung des Breitensuchalgorithmus in PHP. Teilen Sie es wie folgt mit allen als Referenz:

Algorithmische Idee der Breitensuche Breadth-FirstTraversal

Breadth-First Traversal ist eine Traversierungsstrategie für verbundene Graphen. Denn seine Idee besteht darin, von einem Scheitelpunkt V0 aus zu beginnen und zuerst den weiteren Bereich um ihn herum radial zu durchqueren, daher der Name.

Breitensuche-Durchquerung ähnelt der hierarchischen Durchquerung eines Baums. Bei einem ungerichteten verbundenen Graphen beginnt die Breitensuche an einem bestimmten Scheitelpunkt v0 des Graphen. Nach dem Besuch von v0 wird nacheinander nach jedem nicht besuchten benachbarten Punkt w1, w2, ... von v0 gesucht. Suchen Sie dann nacheinander nach jedem nicht besuchten benachbarten Punkt von w1, jedem nicht besuchten benachbarten Punkt von w2, ... Das heißt, beginnend bei v0, von nah nach fern, besuchen Sie die Scheitelpunkte, die mit v0 verbunden sind und eine Pfadlänge von 1, 2, ... haben, nach Ebene, bis alle Scheitelpunkte im verbundenen Diagramm einmal besucht werden.

Solange auf die Scheitelpunkte jeder Ebene in einer bestimmten Reihenfolge zugegriffen wird, ist dies für die Programmimplementierung praktisch. Die allgemeine hierarchische Reihenfolge der Breitensuche ist sicher und die Zugriffsreihenfolge jeder Ebene ist nicht eindeutig .

Die detaillierte Beschreibung lautet wie folgt:

Angenommen, der Anfangszustand von Graph G ist, dass nicht alle Scheitelpunkte besucht wurden und jeder Scheitelpunkt i in G ausgewählt ist als Ausgangspunkt, dann Breitenpriorität. Die Grundidee der Suche ist:

(1) Besuchen Sie einen bestimmten Scheitelpunkt V im Diagramm und zeichnen Sie ihn auf.
(2) Besuchen Sie nacheinander alle benachbarten Scheitelpunkte von V.
(3) Besuchen Sie von diesen benachbarten Punkten aus nacheinander ihre nicht besuchten benachbarten Punkte, bis alle besuchten Scheitelpunkte im Diagramm alle besuchten benachbarten Punkte sind.
(4) Schritt (3).

Und so weiter, bis alle Eckpunkte im Diagramm besucht wurden.

Die Breitensuche muss sich beim Suchen und Zugreifen auf eine Ebene die besuchten Scheitelpunkte merken, sodass sie beim Zugriff auf die Scheitelpunkte der unteren Ebene von den besuchten Scheitelpunkten aus beginnen kann, um die angrenzenden Punkte zu suchen und zu besuchen. Daher muss bei der Breitensuche eine Warteschlange eingerichtet werden, damit die besuchten Scheitelpunkte nacheinander vom Ende der Warteschlange an in die Warteschlange gelangen. Wenn Sie einen Scheitelpunkt einer niedrigeren Ebene suchen und darauf zugreifen, nehmen Sie zuerst einen Scheitelpunkt der oberen Ebene, der vom Teamleiter besucht wurde, heraus und suchen Sie dann von diesem Scheitelpunkt aus nach den angrenzenden Punkten und greifen Sie darauf zu.

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

Anwendung:

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

Das obige ist der detaillierte Inhalt vonDetaillierte Einführung in die Methode zur Implementierung des Breitensuchalgorithmus in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!