<?php
abstract class SearchInterface
{
  protected $G;//圖
  protected $s;//圖的首節(jié)點
  function __construct($_G,$_s){$this->G = $_G;$this->s = $_s;}
  public abstract function search();
}
?>

<?php
include_once('SearchInterface.php');
class bfs extends SearchInterface
{
  private $d = array();//源點s和頂點u之間的距離
  private $tt = array();//結(jié)點u的父母存于變量
  private $visit = array();//已訪問節(jié)點
  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()
  {
    //訪問所有節(jié)點
    $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).'<br>';
          $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;
            }
          }
        }
      }
    }
  }
}
?>

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