Qu'est-ce que l'algorithme de recherche en largeur en premier

L'algorithme de recherche en largeur d'abord est également appelé [recherche en largeur d'abord] ou [recherche en premier horizontal], appelé BFS. Il s'agit d'un algorithme de recherche de graphiques (nécessitant la possibilité d'utiliser des graphiques pour représenter la corrélation de problèmes). BFS est l'un des algorithmes de recherche de graphes les plus simples. Cet algorithme est également le prototype de nombreux algorithmes de recherche de graphes importants.

Quel est l'algorithme de recherche en largeur ? Comment l'implémenter en utilisant PHP ? L'article suivant vous le présentera. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer. J'espère qu'il sera utile à tout le monde.

Breadth-FirstTraversal

Breadth-First Search, également connue sous le nom de «Breadth-First Search» ou «Horizontal first search», appelée BFS ; BFS est un algorithme de recherche de graphiques (nécessite la capacité d'utiliser des graphiques pour exprimer la pertinence des problèmes).

BFS est l'un des algorithmes de recherche de graphes les plus simples. Cet algorithme est également le prototype de nombreux algorithmes de graphes importants.

BFS n'utilise pas de règle empirique. D'un point de vue algorithmique, tous les nœuds enfants obtenus en développant le nœud seront ajoutés à une file d'attente premier entré, premier sorti. Dans une expérience générale, les nœuds dont les nœuds voisins n'ont pas été testés sont placés dans un conteneur dit ouvert (comme une file d'attente ou une liste chaînée), tandis que les nœuds qui ont été testés sont placés dans un conteneur appelé milieu fermé.

Comment implémenter un algorithme de recherche en largeur en php ?

Idée algorithmique de recherche en largeur d'abord

Le parcours en largeur d'abord est une stratégie de parcours pour les 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;
            }
          }
        }
      }
    }
  }
}
?>

Utilisation :

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

Pour plus de connaissances connexes, veuillez visiter Site Web PHP chinois ! !

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!