Was ist der Breitensuchalgorithmus?

Der Breitensuchalgorithmus wird auch [Breitensuche] oder [Horizontalsuche] genannt und als BFS bezeichnet. Es handelt sich um einen Suchalgorithmus für Diagramme (der die Fähigkeit erfordert, Diagramme zur Darstellung der Korrelation von Problemen zu verwenden). BFS ist einer der einfachsten Graphsuchalgorithmen. Dieser Algorithmus ist auch der Prototyp vieler wichtiger Graphsuchalgorithmen.

Was ist der Breitensuchalgorithmus? Wie implementiert man es mit PHP? Der folgende Artikel stellt es Ihnen vor. Es hat einen gewissen Referenzwert. Freunde in Not können sich darauf beziehen. Ich hoffe, es wird für alle hilfreich sein.

Breadth-FirstTraversal

Breadth-First Search, auch bekannt als „Breadth-First Search“ oder „Horizontal First Search“, bezeichnet als BFS; BFS ist ein Suchalgorithmus für Diagramme (erfordert die Fähigkeit, Diagramme zu verwenden, um die Relevanz von Problemen auszudrücken).

BFS ist einer der einfachsten Graph-Suchalgorithmen. Dieser Algorithmus ist auch der Prototyp vieler wichtiger Graph-Algorithmen.

BFS verwendet keinen Faustregelalgorithmus. Aus algorithmischer Sicht werden alle untergeordneten Knoten, die sich aus der Erweiterung des Knotens ergeben, einer First-In-First-Out-Warteschlange hinzugefügt. In einem allgemeinen Experiment werden Knoten, deren Nachbarknoten nicht getestet wurden, in einem Container namens „offen“ (z. B. einer Warteschlange oder einer verknüpften Liste) platziert, während Knoten, die getestet wurden, in einem Container namens „geschlossene Mitte“ platziert werden.

Wie implementiert man einen Breitensuchalgorithmus in PHP?

Algorithmusidee der Breitensuche

Breitenorientierte Durchquerung ist eine Durchquerungsstrategie für verbundene Graphen. Denn seine Idee besteht darin, von einem Scheitelpunkt V0 aus zu beginnen und zuerst den größeren 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 benachbarten 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 Scheitelpunkte auf niedrigerer Ebene suchen und darauf zugreifen, nehmen Sie zunächst einen Scheitelpunkt auf höherer Ebene heraus, der vom Teamleiter besucht wurde, und suchen Sie dann von diesem Scheitelpunkt aus nach den benachbarten 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;
            }
          }
        }
      }
    }
  }
}
?>

Verwendung:

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

Weitere Informationen zu diesem Thema finden Sie unter PHP chinesische Website! !

Das obige ist der detaillierte Inhalt vonWas ist der Breitensuchalgorithmus?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!