9. 深度優(yōu)先搜索和廣度優(yōu)先搜索
關(guān)于搜索&遍歷
對(duì)于搜索來說楚昭，我們絕大多數(shù)情況下處理的都是叫 “所謂的暴力搜索” ，或者是說比較簡(jiǎn)單樸素的搜索拍顷，也就是說你在搜索的時(shí)候沒有任何所謂的智能的情況在里面考慮抚太，很多情況下它做的一件事情就是把所有的結(jié)點(diǎn)全部遍歷一次，然后找到你要的結(jié)果。
基于這樣的一個(gè)數(shù)據(jù)結(jié)構(gòu)尿贫，如果這個(gè)數(shù)據(jù)結(jié)構(gòu)本身是沒有任何特點(diǎn)的电媳，也就是說是一個(gè)很普通的樹或者很普通的圖。那么我們要做的一件事情就是遍歷所有的結(jié)點(diǎn)庆亡。同時(shí)保證每個(gè)點(diǎn)訪問一次且僅訪問一次匾乓，最后找到結(jié)果。
那么我們先把搜索整個(gè)先化簡(jiǎn)情況又谋，我們就收縮到在樹的這種情況下來進(jìn)行搜索拼缝。
如果我們要找到我們需要的一個(gè)值，在這個(gè)樹里面我們要怎么做彰亥？那么毫無疑問就是從根這邊開始先搜左子樹咧七，然后再往下一個(gè)一個(gè)一個(gè)一個(gè)點(diǎn)走過去，然后走完來之后再走右子樹任斋，直到找到我們的點(diǎn)继阻，這就是我們所采用的方式。
再回到我們數(shù)據(jù)結(jié)構(gòu)定義废酷，它只有左子樹和右子樹瘟檩。
我們要實(shí)現(xiàn)這樣一個(gè)遍歷或者搜索的話，毫無疑問我們要保證的事情就是
- 每個(gè)結(jié)點(diǎn)都要訪問一次
- 每個(gè)結(jié)點(diǎn)僅僅要訪問一次
- 對(duì)于結(jié)點(diǎn)訪問的順序不限
- 深度優(yōu)先：Depth First Search
- 廣度優(yōu)先：Breadth First Search
僅訪問一次的意思就是代表我們?cè)谒阉髦谐后。覀儾幌胱鲞^多無用的訪問墨辛，不然的話我們的訪問的效率會(huì)非常的慢。
當(dāng)然的話還可以有其余的搜索趴俘，其余的搜索的話就不再是深度優(yōu)先或者廣度優(yōu)先了睹簇，而是按照優(yōu)先級(jí)優(yōu)先 难咕。當(dāng)然你也可以隨意定義，比如說從中間優(yōu)先類似于其他的東西阀坏，但只不過的話你定義的話要有現(xiàn)實(shí)中的場(chǎng)景读拆。所以你可以認(rèn)為是一般來說就是深度優(yōu)先、廣度優(yōu)先荷愕，另外的話就是優(yōu)先級(jí)優(yōu)先。按照優(yōu)先級(jí)優(yōu)先搜索的話，其實(shí)更加適用于現(xiàn)實(shí)中的很多業(yè)務(wù)場(chǎng)景柜某，而這樣的算法我們一般把它稱為啟發(fā)式搜索，更多應(yīng)用在深度學(xué)習(xí)領(lǐng)域敛纲。而這種比如說優(yōu)先級(jí)優(yōu)先的話喂击，在很多時(shí)候現(xiàn)在已經(jīng)應(yīng)用在各種推薦算法和高級(jí)的搜索算法，讓你搜出你中間最感興趣的內(nèi)容淤翔，以及每天打開抖音翰绊、快手的話就給你推薦你最感興趣的內(nèi)容，其實(shí)就是這個(gè)原因。
深度優(yōu)先搜索（DFS）
遞歸寫法
遞歸的寫法监嗜，一開始就是遞歸的終止條件谐檀，然后處理當(dāng)前的層，然后再下轉(zhuǎn)裁奇。
- 那么處理當(dāng)前層的話就是相當(dāng)于訪問了結(jié)點(diǎn)
node桐猬，然后把這個(gè)結(jié)點(diǎn)node加到已訪問的結(jié)點(diǎn)里面去； - 那么終止條件的話刽肠，就是如果這個(gè)結(jié)點(diǎn)之前已經(jīng)訪問過了溃肪，那就不管了；
- 那么下轉(zhuǎn)的話音五，就是走到它的子結(jié)點(diǎn)惫撰，二叉樹來說的話就是左孩子和右孩子，如果是圖的話就是連同的相鄰結(jié)點(diǎn)放仗，如果是多叉樹的話這里就是一個(gè)
children,然后把所有的children的話遍歷一次润绎。
- 二叉樹模版
def dfs(node):
if node in visited:
# already visited
return
visited.add(node)
# process current node
# ... # logic here
dfs(node.left)
dfs(node.right)
- 多叉樹模版
visited = set()
def dfs(node, visited):
if node in visited: # terminator
# already visited
return
visited.add(node)
# process current node here.
...
for next_node in node.children():
if next_node not in visited:
dfs(next_node, visited)
非遞歸寫法
def DFS(self, tree):
if tree.root is None:
return []
visited, stack = [], [tree.root]
while stack:
node = stack.pop()
visited.add(node)
process (node)
nodes = generate_related_nodes(node)
stack.push(nodes)
# other processing work
...
遍歷順序
我們看深度優(yōu)先搜索或者深度優(yōu)先遍歷的話，它的整個(gè)遍歷順序毫無疑問根節(jié)點(diǎn) 1 永遠(yuǎn)最先開始的诞挨，接下來往那個(gè)分支走其實(shí)都一樣的莉撇，我們簡(jiǎn)單起見就是從最左邊開始走，那么它深度優(yōu)先的話就會(huì)走到底惶傻。
參考多叉樹模版我們可以在腦子里面或者畫一個(gè)圖把它遞歸起來的話棍郎，把遞歸的狀態(tài)樹畫出來，就是這么一個(gè)結(jié)構(gòu)银室。
- 就比如說它開始剛進(jìn)來的話涂佃，傳的是
root的話，root就會(huì)先放到visited里面蜈敢，表示root已經(jīng)被visit,被visited之后就從root.childern里面找next_node辜荠，所有它的next_node都沒有被訪問過的，所以它就會(huì)先訪問最左邊的這個(gè)結(jié)點(diǎn)抓狭，這里注意當(dāng)它最左邊這個(gè)結(jié)點(diǎn)先拿出來了伯病，判斷沒有在visited里面，因?yàn)槌?root之外其他結(jié)點(diǎn)都沒有被visited過否过，那么沒有的話它就直接調(diào)dfs午笛，next_node就是把最左邊結(jié)點(diǎn)放進(jìn)去，再把visited也一起放進(jìn)去苗桂。 - 遞歸調(diào)用的一個(gè)特殊药磺，它不會(huì)等這個(gè)循環(huán)跑完，它就直接會(huì)進(jìn)到下一層了煤伟，也就是當(dāng)前夢(mèng)境的話這里寫了一層循環(huán)癌佩，但是在第一層循環(huán)的時(shí)候木缝，我就要開始下鉆到新的一層夢(mèng)境里面去了。所以在這里的話驼卖，
圖的遍歷順序
廣度優(yōu)先搜索（BFS）
廣度優(yōu)先遍歷它就不再是用遞歸也不再是用棧了氨肌，而是用所謂的隊(duì)列。你可以把它想象成一個(gè)水滴酌畜，滴到1這個(gè)位置怎囚，然后它的水波紋一層一層一層擴(kuò)散出去就行了。
兩者對(duì)比
BFS代碼模版
# Python
def BFS(graph, start, end):
visited = set()
queue = []
queue.append([start])
while queue:
node = queue.pop()
visited.add(node)
process(node)
nodes = generate_related_nodes(node)
queue.push(nodes)
# other processing work
...
部分圖片來源于網(wǎng)絡(luò)桥胞，版權(quán)歸原作者恳守，侵刪。