【算法圖解】個(gè)人學(xué)習(xí)筆記4——DFS深度優(yōu)先算法
定義
深度優(yōu)先搜索算法（英語：Depth-First-Search，DFS）是一種用于遍歷或搜索樹或圖的算法。這個(gè)算法會(huì)盡可能深的搜索樹的分支。當(dāng)節(jié)點(diǎn)v的所在邊都己被探尋過，搜索將回溯到發(fā)現(xiàn)節(jié)點(diǎn)v的那條邊的起始節(jié)點(diǎn)。這一過程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止。如果還存在未被發(fā)現(xiàn)的節(jié)點(diǎn)，則選擇其中一個(gè)作為源節(jié)點(diǎn)并重復(fù)以上過程，整個(gè)進(jìn)程反復(fù)進(jìn)行直到所有節(jié)點(diǎn)都被訪問為止。這種算法不會(huì)根據(jù)圖的結(jié)構(gòu)等信息調(diào)整執(zhí)行策略。
代碼：
#深度優(yōu)先算法
#參考 https://www.bilibili.com/video/BV1Ks411575U/?spm_id_from=333.788.recommend_more_video.0
graph={
"A":["B","C"],
"B":["A","C","D"],
"C":["A","B","D","E"],
"D":["B","C","E","F"],
"E":["C","D"],
"F":["D"]
}
def DFS(graph,s,mb): #mb為用戶查找目標(biāo)元素
? ? ? ?#創(chuàng)建棧
? ? stack=[]
? ? #加入變量起點(diǎn)根s
? ? stack.append(s)
? ? # 鄰居節(jié)點(diǎn)，判斷是否重復(fù)遍歷
? ? seen=set()#創(chuàng)建一個(gè)集合
? ? seen.add(s)#加入
? ? relpace=0#記錄所走步長(zhǎng)
? ? while stack:
? ? ? ? # 添加一個(gè)節(jié)點(diǎn)，比如"A"為vertex
? ? ? ? vertex=stack.pop()
? ? ? ? # 棧后進(jìn)先出，所以是pop（）先出
? ? ? ? # nodes為"A"的臨近節(jié)點(diǎn)
? ? ? ? nodes=graph[vertex]
? ? ? ? #w為遍歷nodes的集合
? ? ? ?
? ? ? ? for w in nodes:
? ? ? ? ? ? ?
? ? ? ? ? ? if w not in seen:
? ? ? ? ? ? ? ? # 如果w不在seen中，w則加入集合和字典
? ? ? ? ? ? ? ? stack.append(w)
? ? ? ? ? ? ? ? seen. add(w)
? ? ? ? ? ? ? ? ? ? ?
? ? ? ? # 當(dāng)遍歷到F ? ? ? ?
? ? ? ? if vertex==mb:
? ? ? ? ? ? break ?
? ? ? ? print(vertex) ? ?
? ? ? ? relpace +=1
? ? ? ? if relpace>6:
? ? ? ? ? ? print("不存在要遍歷的玩意")
? ? print("大O表示法查找時(shí)長(zhǎng)為{}".format(relpace))
DFS(graph,"A","F")
