定義

深度優(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")