BFS

思路：

利用隊列實現(xiàn)
創(chuàng)建一個空隊列，加入首節(jié)點的拓展
新建一個空列表，用于后邊的判重
如果沒用重復(fù)，然后比對，符合返回，不符合加到隊列尾部
遍歷完所有隊列數(shù)據(jù)，如果沒有符合的，返回False

from collections import deque
def search(name):#廣度優(yōu)先搜索(BFS)
    #deque()函數(shù)創(chuàng)建一個雙端隊列（先進(jìn)先出）
    #注意deque是python標(biāo)準(zhǔn)庫cillections中的一個模塊
    search_quene = deque()
    search_quene += graph[name]
    #創(chuàng)建空列表的目的：為了防止后邊添加到隊列里的元素與之前的重復(fù)出現(xiàn)
    #所以我加入一個空列表，將判斷完成的數(shù)據(jù)添加的這個列表，將準(zhǔn)備進(jìn)入列表的數(shù)據(jù)與這個列表元素對比，確保沒有重復(fù)元素再次進(jìn)入隊列，防止無限循環(huán)產(chǎn)生
    searched = []
    while search_quene:
    #隊列中，pop()默認(rèn)拋出右邊元素，但是我們希望，append()從右邊入隊，popleft()從左邊出隊
        person = search_quene.popleft()
        if person not in searched:
        #person_is_not()是一個判斷函數(shù)，我們需要判斷我們查找的內(nèi)容是否滿足我們的需求
            if person_is_not(person):
                print (person+" is this")
                return True
            else:
                search_quene += graph[person]
                searched.append(person)
    return False

DFS

思路：

在這里插入圖片描述

利用棧實現(xiàn)
每次從棧的末尾彈出一個元素，搜索所有在它下一級的元素，把這些元素壓入棧中。并把這個元素記為它下一級元素的前驅(qū)。
如圖，我們以A為首節(jié)點，然后找到B節(jié)點，然后再找到D節(jié)點，D節(jié)點再無子節(jié)點，然后放回上一節(jié)點，然后在找到E節(jié)點，再無子節(jié)點返回上一節(jié)點，B的子節(jié)點全部便利后繼續(xù)返回，然后找到C節(jié)點，F(xiàn)節(jié)點，G節(jié)點

def dfs(node):
    if node is None:
        return
    nodeSet = set()
    stack = []
    print(node.value)
    nodeSet.add(node)
    stack.append(node)
    while len(stack)>0:
        cur = stack.pop()
        for next in cur.nexts:
            if next not in nodeSet:
                stack.append(cur)
                stack.append(next)
                set.add(next)
                print(next.value)
                break