Detailed introduction to the method of implementing breadth-first search algorithm in PHP

This article mainly introduces the implementation of breadth-first search algorithm (BFS, Broad First Search) in PHP. It briefly describes the principle of breadth-first search algorithm and analyzes the steps and related operating techniques of implementing breadth-first search algorithm in PHP based on specific examples. , Friends in need can refer to

This article describes the implementation of breadth-first search algorithm in PHP. Share it with everyone for your reference, as follows:

Algorithmic Thoughts of Breadth-First Search Breadth-FirstTraversal

Breadth-First Traversal is a traversal strategy for connected graphs. Because its idea is to start from a vertex V0 and radially traverse the wider area around it first, hence the name.

Breadth-first search traversal is similar to hierarchical traversal of a tree. For an undirected connected graph, the breadth-first search starts from a certain vertex v0 of the graph. After visiting v0, it sequentially searches for each unvisited adjacent point w1, w2,... of v0. Then sequentially search for each unvisited adjacent point of w1, each unvisited adjacent point of w2,... That is, starting from v0, from near to far, visit the vertices that have paths connected to v0 and the path lengths are 1, 2,... in sequence, until all vertices in the connected graph are visited once.

As long as the vertices of each layer are accessed in a certain order, it is convenient for program implementation. The overall hierarchical order of breadth-first search is certain, and the access order of each layer is not unique.

The specific description is as follows:

Assume that the initial state of graph G is that all vertices have not been visited, and any vertex i in G is selected as the initial point, then breadth priority The basic idea of ​​search is:

(1) Access and record from a certain vertex V in the graph.
(2) Visit all adjacent vertices of V in sequence;
(3) Starting from these adjacent points, visit their unvisited adjacent points in sequence until all the visited vertices in the graph are All adjacent points are visited.
(4) Step (3).

And so on until all vertices in the graph have been visited.

Breadth-first search needs to remember the visited vertices when searching and accessing a layer, so that when accessing the lower-level vertices, it starts from the visited vertices to search and visit its adjacent points. Therefore, in breadth-first search, a queue needs to be set up so that the visited vertices enter the queue sequentially from the end of the queue. When searching and accessing lower-level vertices, first take out an upper-level vertex that has been visited from the head of the team, and then search and access its adjacent points starting from this vertex.

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();

The above is the detailed content of Detailed introduction to the method of implementing breadth-first search algorithm in PHP. For more information, please follow other related articles on the PHP Chinese website!