算法学习笔记–广度优先搜索(1)

解决最短路径问题的步骤

两个步骤 1. 使用图来建立问题模型 2. 使用广度优先搜索解决问题

什么是图？

图用于模拟一组连接。 图由节点和边组成。直接相连的节点称为邻居。

当图是有向图的时候A–>B（A指向B）那么B是A的邻居，A不是B的邻居。

当图是无向图的时候A—B，他们互为邻居。

广度优先算法是什么？可以解决哪些问题？

1）广度优先搜索是一种用于图的查找算法。

2）第一类问题：从节点A出发，有前往节点B的路径吗？ 第二类问题：从节点A出发，前往B的哪条路径最短？

可以发现要解决第二类问题，首先要考虑第一类问题的答案是否成立。

如何查找最短路径

一圈一圈向外辐射查找

实现图

可以使用散列表实现，也就是python中的字典。

实现查找

使用队列（deque） 为了避免陷入死循环，所以我们要加入一个判断一个值是否已经被查找过了。可以使用一个列表存储已经被查找过的值。

运行时间

O(V + E) V: 顶点 E：边数

实现

from collections import deque graph = {} 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_seller(person): print person + 'is a mango seller!' return Ture else: search_queue += graph[person] searched.append(person) return False def person_is_seller(name): pass