一、简介
1、定义
广度优先搜索（Breadth-First Search）是最简便的图的搜索算法之一，又称宽度优先搜索，这一算法也是很多重要的图算法的原型。广度优先搜索属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
2、应用
广度优先搜索被用于解决最短路径问题（shortest-path problem）。
广度优先搜索让你能够找出两样东西之间的最短距离，不过最短距离的含义有很多！使用广度优先搜索可以：
- 编写国际跳棋AI，计算最少走多少步就可获胜；
- 编写拼写检查器，计算最少编辑多少个地方就可将错拼的单词改成正确的单词，如将READED改为READER需要编辑一个地方；
- 根据你的人际关系网络找到关系最近的医生。
3、图简介
既然广度优先搜索是作用于图的一种算法，这里对图作一个简单的介绍，先不深入了解。
图由节点和边组成。一个节点可能与多个节点相连，这些节点被称为邻居。
二、实现原理
广度优先算法的核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点……，如此依次扩展，检查下去，直到发现目标节点为止。即
- 从图中的某一顶点V0开始，先访问V0；
- 访问所有与V0相邻接的顶点V1，V2，......，Vt；
- 依次访问与V1，V2，......，Vt相邻接的所有未曾访问过的顶点；
- 循此以往，直至所有的顶点都被访问过为止。
广度优先搜索使用队列（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
网友评论