python（九）：广度优先搜索

一、散列表、链表、数组、栈与队列

散列表的另称为字典，是一种重要的数据结构，元素包含键和值，两者是映射关系广泛应用于查找和图算法中，字典的创建如下：

a = {}

##或者

a = dict()

以上两者都是创建一个空的散列表的方式，字典的读取速度接近于数组，插入速度接近于链表。

链表是一种储存元素地址的数据结构，指向地址，但是链表可以隔开存储，就像去电影院一样，隔开坐，但是链表的插入速度很快，读取速度很慢。

数组类似于链表，但是数组就像去电影院看电影的情侣一样是不愿意分开坐的，内存分配必须连续的，数组的读取速度很快，插入速度很慢。

链表和数组的python实现方式后续研究。

栈类似于便签，后面写的总在最上面，处理顺序是后入先出；栈的使用在python中随处可见，如函数的调用等，都是基于栈的处理顺序和理论。

队里类似于排队，后面进入的后面处理，处理顺序是先入先出。

from collections import deque

deque = deque()

python中实现队列需要使用deque函数调用。

二、广度优先搜索

广度优先搜索用于解决多个路径最少路径的问题，使用图的数据结构，且图均为非加权图。

案例：查找人际关系中是否有销售员；采用队列及广度优先搜索

graph = {}

graph["you"] = ["alice", "bob", "claire"]
graph["alice"] = []
graph["bob"] = ["tom"]
graph["tom"] = []
graph["claire"] = []

def person_is_seller(name):
    return name[-1] == 'm'

from collections import deque
def search(name):
    search_q = deque()
    search_q += graph(name)
    searched = []

    while search_q:
        person = search_q.popleft()
        if person not in searched:
            if person_is_seller(person):
                print(person+" is a seller")
                return True
            else:
                search_q += graph(person)
                searched.append(person)
        return False

使用广度优先搜索时，已经搜索过的元素需要在下一次搜索中剔除，所以用到函数 popleft()，否则将出现无限循环。

popleft 仅能在队列中使用，不能再数组、链表、字典中使用，且 popleft 处理过后的原队列中的元素将出列，如下图所示：