广度优先搜索-
- 广度优先搜索 是一种图算法。
- 解决最短路径问题的算法被称为广度优先搜索。
- 图：
- 图由节点和边组成。一个节点可能与众多节点直接项链，这些节点被称为邻居。
- 可以使用图模拟不同的东西是如何相连的。
- 广度优先搜索是一种用于图的查找算法，可以帮助回答两类问题。
第一，从节点A出发，有前往节点B的路径吗？
第二，从节点A出发，前往节点B的哪条路径最短？
- 在广度优先搜索的执行过程中,搜索范围从起点开始逐渐向外延伸,即先检查一度关系,再检查二度关系。
- 广度优先搜索的运行时间为
O(人数 + 边数),这通常写作O(V + E),其中V为顶点(vertice)数,E为边数。
队列和栈
- 队列是一种先进先出(First In First Out,FIFO)的数据结构
- 栈是一种后进先出(Last In First Out,LIFO)的数据结构
图
- 有指向关系的这被称为有向图(directed graph),其中的关系是单向的。
- 无向图(undirected 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 True
else:
search_queue += graph[person]
searched.append(person)
#将这个人标记为检查过
return False
search("you")