欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

浅谈广度优先搜索算法

程序员文章站 2022-06-11 21:35:11
...

广度优先搜索

广度优先搜索可以让我们找出两个东西之间的最短距离,比如在在中国象棋中计算最少花费多少步就可以把对方将死、前往朋友家的最短路径、根据人际关系网络找到关系最近的代理商等等。

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(边数+人数)