Introduction détaillée à la méthode d'implémentation de l'algorithme de recherche en largeur en PHP

Cet article présente principalement l'implémentation de l'algorithme de recherche en largeur (BFS, Broad First Search) en PHP. Il décrit brièvement le principe de l'algorithme de recherche en largeur et analyse les étapes et les techniques de fonctionnement associées à la mise en œuvre de la recherche en largeur. algorithme en PHP avec des exemples spécifiques, Les amis dans le besoin peuvent se référer à

Cet article décrit la mise en œuvre de l'algorithme de recherche en largeur en PHP. Partagez-le avec tout le monde pour votre référence, comme suit :

Idée algorithmique de recherche en largeur d'abord Breadth-FirstTraversal

Breadth-First Traversal est une stratégie de traversée pour graphiques connectés. Parce que son idée est de partir d’un sommet V0 et de parcourir d’abord radialement la zone plus large qui l’entoure, d’où son nom.

Le parcours de recherche en largeur d'abord est similaire au parcours hiérarchique d'un arbre. Pour un graphe connecté non orienté, la recherche en largeur commence à partir d'un certain sommet v0 du graphe. Après avoir visité v0, elle recherche séquentiellement chaque point adjacent non visité w1, w2,... de v0. Recherchez ensuite séquentiellement chaque point adjacent non visité de w1, chaque point adjacent non visité de w2,... Autrement dit, à partir de v0, de près vers loin, visitez les sommets connectés à v0 et dont les longueurs de chemin sont de 1, 2,... par niveau, jusqu'à ce que tous les sommets du graphe connecté soient visités une fois.

Tant que les sommets de chaque couche sont accessibles dans un certain ordre, cela est pratique pour la mise en œuvre du programme. L'ordre hiérarchique global de la recherche en largeur est certain et l'ordre d'accès de chaque couche n'est pas unique. .

La description détaillée est la suivante :

Supposons que l'état initial du graphe G est que tous les sommets n'ont pas été visités et que tout sommet i dans G est sélectionné comme point initial, puis priorité en largeur L'idée de base de la recherche est la suivante :

(1) Visiter et enregistrer à partir d'un certain sommet V dans le graphique.
(2) Visitez tous les sommets adjacents de V dans l'ordre ;
(3) À partir de ces points adjacents, visitez leurs points adjacents non visités dans l'ordre jusqu'à ce que tous les sommets visités dans le graphique soient tous les points adjacents visités.
(4) Étape (3).

Et ainsi de suite jusqu'à ce que tous les sommets du graphique aient été visités.

La recherche en largeur doit se souvenir des sommets visités lors de la recherche et de l'accès à une couche, de sorte que lors de l'accès aux sommets de niveau inférieur, elle puisse partir des sommets visités pour rechercher et visiter ses points adjacents. Par conséquent, dans une recherche en largeur d'abord, une file d'attente doit être configurée pour que les sommets visités entrent dans la file d'attente séquentiellement à partir de la fin de la file d'attente. Lors de la recherche et de l'accès à un sommet de niveau inférieur, supprimez d'abord un sommet de niveau supérieur qui a été visité par le chef de l'équipe, puis recherchez et accédez à ses points adjacents à partir de ce sommet.

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

Comment utiliser :

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!