浅谈广度优先搜索算法
广度优先搜索
广度优先搜索可以让我们找出两个东西之间的最短距离,比如在在中国象棋中计算最少花费多少步就可以把对方将死、前往朋友家的最短路径、根据人际关系网络找到关系最近的代理商等等。
1、引言
假设你要找出一条从你家到学校的路线,并且想找出一条最短的路线,你可以选择的路线如下:
那么我们该怎么找呢?
首先我们看我们从家出发,一步能到学校吗?
显然一步是到达不了的,那两步呢?
看来两步也不能,那三步呢?
看来三步可以到达学校,于是我们就找出了从家到学校的最短路线。一般来说,解决最短路径问题的算法被称为广度优先搜索。
2、广度优先搜索能解决的问题
广度优先搜索一般能解决以下两类问题:
1、从A节点出发,有没有前往B节点的路径?
假设你是一名农场主,家里有五百亩稻田,到了收获的季节,你急需找一名大米经销商,来出售你的稻谷。那么你会怎么做呢?
首先你肯定会先看看你的朋友有没有干这一行的,假如你的朋友没有干这一行的,那么你可能会在你朋友的朋友当中去查找。如果还没有的话呢?那么你可能在朋友的朋友当中进行查找,直到搜索完你整个人际关系网,或者找到大米经销商为止。
这使用的就是广度优先搜索算法。
2、从A节点出发,前往B节点的哪条路径最短?
我们接着使用上面的那个例子,先提前说明一下,你的朋友是一度关系,朋友的朋友是二度关系。也就是一度关系比二度关系更近一步,二度关系比三度关系更近一步,以此类推。
要想找出最短的路径,那么你首先应该从一度关系中查找,并确定里面有没有大米经销商。在确定其中没有大米经销商后,才从二度关系中进行查找,以此类推。这就是我们广度优先搜索的执行过程,即搜索范围从起点开始逐渐向外延伸,即先检查一度关系,然后再检查二度关系。在一度关系全部检索完成之后,再检索二度关系。因为我们要找的是最短路径。
3、广度优先搜索算法的实现
那么要实现上述算法,我们该怎么操作呢?相信我们不难发现,要实现上面的过程,我们只有按照添加顺序查找时,才有可能实现目的。也就是说,A,B,C,D先于F,G,E,那么我们应该先检查A,B,C,D,然后再检查F,G,E。要实现这个操作,那么我们就需要用到队列的知识了。
队列的工作原理就如它的名字一样。相信我们大家都等过公交车,我们在上公交车之前都是站成一排的,先排队的先上车,后排队的后上车。队列也是这样,它是一种先进先出的数据结构
下面我就用伪代码来实现广度优先搜索算法
from collections import deque
queue = deque()
queue += graph["you"]
//用于记录检查过的人
def search(name):
search_queue = deque()
search_queue += graph[name]
searched = []
//人际关系网
graph = {}
graph["you"] = ["A","B","C","D"]
graph["A"] = ["F","G"]
graph["B"] = ["G"]
graph["C"] = []
graph["D"] = ["E"]
while queue:
person = queue.popleft()
if person not in searched:
if seller(person):
print("find it!!!")
print("The person is "+person)
return True
else:
queue +=graph[person]
searched.append(person)
return False
search("you")
4、运行时间
无论我们讨论什么算法,我们都要考虑它的操作时间。那么我们广度优先搜索算法的操作时间为多少呢?我们从图可知,我们的操作时间是O(边数+人数)