常见算法5、广度优先搜索 Breadth-First Searc

一、简介

1、定义

广度优先搜索（Breadth-First Search）是最简便的图的搜索算法之一，又称宽度优先搜索，这一算法也是很多重要的图算法的原型。广度优先搜索属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

2、应用

广度优先搜索被用于解决最短路径问题（shortest-path problem）。

广度优先搜索让你能够找出两样东西之间的最短距离，不过最短距离的含义有很多！使用广度优先搜索可以：

1. 编写国际跳棋AI，计算最少走多少步就可获胜；
2. 编写拼写检查器，计算最少编辑多少个地方就可将错拼的单词改成正确的单词，如将READED改为READER需要编辑一个地方；
3. 根据你的人际关系网络找到关系最近的医生。

3、图简介

既然广度优先搜索是作用于图的一种算法，这里对图作一个简单的介绍，先不深入了解。

图由节点和边组成。一个节点可能与多个节点相连，这些节点被称为邻居。

二、实现原理

广度优先算法的核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点……，如此依次扩展，检查下去，直到发现目标节点为止。即

1. 从图中的某一顶点V0开始，先访问V0；
2. 访问所有与V0相邻接的顶点V1，V2，......，Vt；
3. 依次访问与V1，V2，......，Vt相邻接的所有未曾访问过的顶点；
4. 循此以往，直至所有的顶点都被访问过为止。

广度优先搜索使用队列（queue）来实现，整个过程也可以看做一个倒立的树形。

三、代码实现：

例：假如你需要在你的人际关系网中寻找是否有职业为医生的人，图如下：

算法图解

而使用广度优先搜索工作原理大概如下 ：

1、Python 3 ：

#使用函数deque来创建一个双端队列
from collections import deque

#假设名字最后一个字母为‘j’的人就是医生
def person_is_doctor(name):
      return name[-1] == 'j'

# 你的人际关系网数据
graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []

def search(name):
    search_queue = deque()
    search_queue += graph[name]
    searched = [] # 这个数组用于记录检查过的人
    while search_queue: #只要队列不为空
        person = search_queue.popleft() # 取出队列中的第一个人
        if not person in searched:
            if person_is_doctor(person):
                print(person + " is a Doctor!")
                return True
            else:
                search_queue += graph[person] # 把这个人的朋友加入队列
                searched.append(person) # 标记检查过的人
    return False

search("you")

=============== 运行结果：===============
anuj is a Doctor!

2、PHP ：

#广度优先搜索 Breadth-First Search    
function personIsDoctor(string $name) {
    return $name[-1] == "j";
}

$graph = [];
$graph["you"] = ["alice", "bob", "claire"];
$graph["bob"] = ["anuj", "peggy"];
$graph["alice"] = ["peggy"];
$graph["claire"] = ["thom", "jonny"];
$graph["anuj"] = [];
$graph["peggy"] = [];
$graph["thom"] = [];
$graph["jonny"] = [];

//SplQueue 类通过使用一个双向链表来提供队列的主要功能。
function enqueue(\SplQueue $queue, array $persons) {
    foreach ($persons as $person) {
        //方法SplQueue::enqueue(mixed $value) 向队列添加一个元素
        $queue->enqueue($person); 
    }
}

function search(string $name) {
    global $graph;
    $searchQueue = new \SplQueue();
    enqueue($searchQueue, $graph[$name]);
    $searched = []; //这个数组用于记录检查过的人
    while (!$searchQueue->isEmpty()) {
        $person = $searchQueue->dequeue();
        if (!isset($searched[$person])) {
            if (personIsDoctor($person)) {
                printf("%s is a doctor", $person);
                return true;
            } else {
                enqueue($searchQueue, $graph[$person]);
                $searched[$person] = true;
            }
        }
    }
    return false;
}

search("you");

=============== 运行结果：===============
anuj is a doctor

参考

1、《算法图解》https://www.manning.com/books/grokking-algorithms
2、SplQueue类：https://www.php.net/manual/zh/class.splqueue.php