Python广度优先查找和深度优先查找(内附python教程分享)

图,特别是图的ADT(抽象数据类型)在计算机科学和数学领域是应用非常广泛的。

图基本认识

图模拟一组连接,假如你在A点,你到B点的路径,可以使用图来代表。

Python广度优先查找和深度优先查找(内附python教程分享)

graph.png

图由图由顶点(vertex,node)和边(edge)组成。一个顶点(vertex)可以与多个顶点连接,通过一条线,这条线称为边(edge)。

图用于模拟一组数据是如何连接的

在Python中使用字典来实现这种连接关系。在之前的文章,我已經介绍了Python字典的实现原理。

广度优先搜索(breadth-first search, BFS)

首先,BFS可以解决两种问题

  1. 从节点A出发,能不能到节点X?
  2. 从节点A出发,到节点X的最短路径是哪条?

如何理解广度:

假如现在你需要在你的朋友的关系网中,找到一个卖芒果的,应该如何做?下图是你的朋友关系网的情况。

Python广度优先查找和深度优先查找(内附python教程分享)

friends.jpg

广度优先,就是, 在你的关系网中,一度关系胜过二度关系。广度优先,就是先在一度关系中找到,再往外层的度找。

现在我们用BFS来解决第一个问题。

这里参考了《算法图解》的例子。

先把上图写为对应的Python代码:

graph = dict()
graph['your'] = ['alice', 'boob', 'claire']
graph['boob'] = ['anuj', 'peggy']
graph['alice'] = ['peggy']
graph['claire'] = ['thom', 'jonny']
graph['anuj'] = []
graph['peggy'] = []
graph['thom'] = []
graph['jonny'] = []

我们使用队列(FIFO)的思想,将关系网的人加入到队列,然后弹出一个元素,并且把该元素的关系网的朋友也加入到队列。下面是代码实现:

def person_is_seller(name):
 return name[-1] == 'm'
def search(graph, name):
 search_queue = deque()
 search_queue += graph[name]
 searched = []
 while search_queue:
 person = search_queue.popleft()
 if person not in search_queue:
 if person_is_seller(person):
 print(searched)
 print(person + ' is a mango seller')
 return True
 else:
 search_queue += graph[person]
 searched.append(person)
 return False

这样的代码只是告诉了我们,在关系网中能够找到那个人(以m字母结尾),并且可以得到那个人的信息。

上面的代码还是比较简单的,现在我们来解决第二个问题,最短路径是哪个?也就是,如何把走过的路径保存起来?

def bfs2(graph, start):
 queue = [(start, [start])] # ['your', ['your']]
 while queue:
 (vertex, path) = queue.pop(0)
 for next_friend in graph[vertex]:
 if person_is_seller(next_friend):
 yield path + [next_friend]
 else:
 queue.append((next_friend, path + [next_friend]))

我们使用列表模拟队列也是一样的, 你也可以使用列表来代替yield。这里其实还有一个问题,就是可能会重复计算。因为并没有像之前那样,把查找过的路径进行判断。由于我们的graph的数据只是单指向的,所以也并不会有什么问题,并且,这样更容易理解一些。下面解释了上面的代码做了什么:

  • 在queue里面存储每一个人(在图论中称为顶点,vertex),以及它的路径,用一个元组包裹。
  • 循环这个queue,每次只弹出最先进去的元素,得到一个元组(顶点,路径)
  • 根据元组的顶点得到graph的数据(朋友的朋友),遍历这些朋友
  • 如果不是要找的芒果商,那么把该朋友也添加到队列里面去,同时把路径也保存。
  • 在if判断加===,在else加打印queue,再给jonny添加一位朋友
graph['jonny'] = ['abcem']
[('alice', ['your', 'alice'])]
[('alice', ['your', 'alice']), ('boob', ['your', 'boob'])]
[('alice', ['your', 'alice']), ('boob', ['your', 'boob']), ('claire', ['your', 'claire'])]
[('boob', ['your', 'boob']), ('claire', ['your', 'claire']), ('peggy', ['your', 'alice', 'peggy'])]
[('claire', ['your', 'claire']), ('peggy', ['your', 'alice', 'peggy']), ('anuj', ['your', 'boob', 'anuj'])]
[('claire', ['your', 'claire']), ('peggy', ['your', 'alice', 'peggy']), ('anuj', ['your', 'boob', 'anuj']), ('peggy', ['your', 'boob', 'peggy'])]
===
[('peggy', ['your', 'alice', 'peggy']), ('anuj', ['your', 'boob', 'anuj']), ('peggy', ['your', 'boob', 'peggy']), ('jonny', ['your', 'claire', 'jonny'])]
===
[['your', 'claire', 'thom'], ['your', 'claire', 'jonny', 'abcem']]

可以看到,最近一度的朋友总是会被先探测到。这就是广度优先查找。

到此,基本的广度优先查找算法已经实现。

深度优先查找

深度优先查找,只要把队列变成栈即可。

def dfs(graph, start):
 queue = [(start, [start])] # 1: ['A', ['A']]
 paths = []
 while queue:
 (vertex, path) = queue.pop()
 for next_friend in graph[vertex]:
 if person_is_seller(next_friend):
 print('===')
 paths.append(path + [next_friend])
 else:
 queue.append((next_friend, path + [next_friend]))
 print(queue)
 return paths
  • 第一次, 会把your三个朋友压入栈
  • 弹出后入栈的朋友,找到他的朋友,再添加入栈,以此类推,每次出栈都会是最新添加的

由于每次出栈的都是新的数据,所以会深入一条一条朋友网的线找下去。这就是深度优先。

最后,想学习Python的小伙伴们!

请关注+私信回复:“学习”就可以拿到一份我为大家准备的Python学习资料!

Python广度优先查找和深度优先查找(内附python教程分享)

pytyhon学习资料

Python广度优先查找和深度优先查找(内附python教程分享)

python学习资料

相关推荐