What is breadth first search algorithm

The breadth-first search algorithm is also called [breadth-first search] or [horizontal-first search], referred to as BFS. It is a search algorithm for graphs (requiring the ability to use graphs to represent the correlation of problems). BFS is one of the simplest graph search algorithms. This algorithm is also the prototype of many important graph search algorithms.

What is the breadth first search algorithm? How to implement it using PHP? The following article will introduce it to you. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to everyone.

Breadth-First Traversal

#Breadth-First Search algorithm (Breadth-First Search), also known as "Breadth-First Search" or "Horizontal first search", referred to as BFS; BFS is a search algorithm for graphs (requires the ability to use graphs to express the relevance of problems).

BFS is one of the simplest graph search algorithms. This algorithm is also the prototype of many important graph algorithms.

BFS does not use a rule of thumb algorithm. From an algorithmic point of view, all child nodes resulting from expanding the node will be added to a first-in, first-out queue. In a general experiment, nodes whose neighbor nodes have not been tested are placed in a container called open (such as a queue or linked list), while nodes that have been tested are placed in a container called closed. middle.

How to implement breadth-first search algorithm in php?

Algorithmic idea of ​​breadth-first search

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

For more related knowledge, please visit PHP Chinese net! !

The above is the detailed content of What is breadth first search algorithm. For more information, please follow other related articles on the PHP Chinese website!