算法学习二十四、深度和广度优先搜索

什么是“搜索”算法?

算法是作用于具体数据结构之上的,深度优先搜索算法和广度优先搜索算法都是基于“图”这种数据结构的。

图有两种主要存储方法,邻接表和邻接矩阵。下面是邻接表存储图的实现代码。

class Graph
{
    /**
     * 顶点个数
     *
     * @var integer
     */
    protected $v;


    /**
     * 邻接表
     *
     * @var array
     */
    protected $adj;


    /**
     * 深度优先搜索是否找到标识位
     *
     * @var boolean
     */
    protected $found = false;


    public function __construct($v)
    {
        $this->v    = $v;
        $this->adj  = [];
        for ($i = 0; $i < $v; $i++) {
            $this->adj[$i] = [];
        }
    }


    public function addEdge($s, $t)
    {
        array_push($this->adj[$s], $t);
        array_push($this->adj[$t], $s);
    

广度优先搜索(BFS)

广度优先搜索(Breadth-First-Search),我们平常都把简称为 BFS。直观地讲,它其实就是一种“地毯式”层层推进的搜索策略,即先查找离起始顶点最近的,然后是次近的,依次往外搜索。

下面是代码实现

public function bfs($s, $t)
{
    if ($s == $t) {
        return;
    }
    $visited = [];
    for ($i = 0; $i < $this->v; $i++) {
        $visited[$i] = null;
    }
    $visited[$s]    = true;
    $queue          = [];
    array_push($queue, $s);
    $prev           = [];
    for ($i = 0; $i < $this->v; $i++) {
        $prev[$i] = -1;
    }
    while (count($queue) > 0) {
        $w = array_shift($queue);
        for ($i = 0; $i < count($this->adj[$w]); $i++) {
            $q = $this->adj[$w][$i];
            if (empty($visited[$q])) {
                $visited[$q] = true;
                $prev[$q]    = $w;
                if ($q == $t) {
                    $this->print($prev, $s, $t);
                    return;
                }
                array_push($queue, $q);
            }
        }
    }
}


public function print($prev, $s, $t)
{
    if ($prev[$t] != -1 && $t != $s) {
        $this->print($prev, $s, $prev[$t]);
    }
    echo $t . " ";
}

visited 是用来记录已经被访问的顶点,用来避免顶点被重复访问。如果顶点 q 被访问,那相应的 visited[q]会被设置为 true。

queue 是一个队列,用来存储已经被访问、但相连的顶点还没有被访问的顶点。因为广度优先搜索是逐层访问的,也就是说,我们只有把第 k 层的顶点都访问完成之后,才能访问第 k+1 层的顶点。当我们访问到第 k 层的顶点的时候,我们需要把第 k 层的顶点记录下来,稍后才能通过第 k 层的顶点来找第 k+1 层的顶点。所以,我们用这个队列来实现记录的功能。

prev 用来记录搜索路径。当我们从顶点 s 开始,广度优先搜索到顶点 t 后,prev 数组中存储的就是搜索的路径。不过,这个路径是反向存储的。prev[w]存储的是,顶点 w 是从哪个前驱顶点遍历过来的(假如能找到路径的话,最终会找到 s 为初始顶点)。比如,我们通过顶点 2 的邻接表访问到顶点 3,那 prev[3]就等于 2。为了正向打印出路径,我们需要递归地来打印,你可以看下 print() 函数的实现方式。

深度优先搜索(DFS)

深度优先搜索(Depth-First-Search),简称 DFS。最直观的例子就是“走迷宫”。

假设你站在迷宫的某个岔路口,然后想找到出口。你随意选择一个岔路口来走,走着走着发现走不通的时候,你就回退到上一个岔路口,重新选择一条路继续走,直到最终找到出口。这种走法就是一种深度优先搜索策略。

下面是代码实现

public function bfsDepth($s, $t)
{
    $this->found = false;
    if ($s == $t) {
        return;
    }
    $visited = [];
    for ($i = 0; $i < $this->v; $i++) {
        $visited[$i] = null;
    }
    $prev    = [];
    for ($i = 0; $i < $this->v; $i++) {
        $prev[$i] = -1;
    }
    $visited[$s] = true;
    $this->recurDfs($s, $t, $visited, $prev);
    $this->print($prev, $s, $t);
}


protected function recurDfs($w, $t, &$visited, &$prev)
{
    if ($this->found == true) {
        return;
    }
    $visited[$w] = true;
    if ($w == $t) {
        $this->found = true;
        return;
    }
    for ($i = 0; $i < count($this->adj[$w]); $i++) {
        $q = $this->adj[$w][$i];
        if (empty($visited[$q])) {
            $prev[$q] = $w;
            $this->recurDfs($q, $t, $visited, $prev);
        }
    }
}