一乌奇、BFS與DFS簡介
在理解動(dòng)態(tài)規(guī)劃没讲、BFS和DFS一文中，已經(jīng)集合具體例子华弓，介紹了圖的BFS與DFS食零。但是比較復(fù)雜，這里就寫的簡單點(diǎn)吧寂屏。
BFS：每次輸出一行贰谣，所用數(shù)據(jù)結(jié)構(gòu)為隊(duì)列
設(shè)想我們每次都從左到右、從上到下的去遍歷一個(gè)圖迁霎，那么就需要把一行中最左邊先進(jìn)來的先輸出吱抚，最右邊后進(jìn)來的后輸出。所以會(huì)用到隊(duì)列考廉。
DFS：每次深挖到底秘豹，所用數(shù)據(jù)結(jié)構(gòu)為棧
設(shè)想我們從圖的最上邊先按照一條道深挖到最下面，在挖到底以后就需要再逐個(gè)返回到上面的頂點(diǎn)昌粤，再去遍歷父節(jié)點(diǎn)是不是還有別的子節(jié)點(diǎn)既绕。后進(jìn)先出的模式，所以需要用到棧涮坐。
因?yàn)檫@是在圖中凄贩，所以，一個(gè)頂點(diǎn)的相鄰點(diǎn)可能包含著已經(jīng)搜索過的點(diǎn)袱讹，因此這兩個(gè)遍歷都需要加一個(gè)集合nodeSet疲扎，里面是已經(jīng)遍歷過的點(diǎn)。在搜索過程中捷雕，如果發(fā)現(xiàn)新的節(jié)點(diǎn)已經(jīng)存在于nodeSet中椒丧，那么就不對新節(jié)點(diǎn)進(jìn)行搜索了。
而救巷，如果是在樹中用BFS與DFS壶熏，因?yàn)橐粋€(gè)節(jié)點(diǎn)頂多有兩個(gè)子節(jié)點(diǎn)，我們已經(jīng)明確知道這個(gè)節(jié)點(diǎn)除了子節(jié)點(diǎn)以外不會(huì)再有相鄰節(jié)點(diǎn)征绸，因此在搜索過程中也不會(huì)遇到重復(fù)的節(jié)點(diǎn)久橙，所以不需要加nodeSet。只需要按照BFS與DFS的思想與所用數(shù)據(jù)結(jié)構(gòu)管怠，遍歷即可淆衷。
二、代碼實(shí)現(xiàn)
參考 圖的廣度優(yōu)先搜索（BFS）與深度優(yōu)先搜索（DFS） Python實(shí)現(xiàn)
2.1渤弛、樹的廣度優(yōu)先搜索
因?yàn)槭菢渥Ｕ總€(gè)node至多有兩個(gè)子節(jié)點(diǎn)，而下面代碼中語句是對圖中不確定的子節(jié)點(diǎn)個(gè)數(shù)來說的，因此下面的這句
for next in cur.nexts:
都可以用對左右兩個(gè)子節(jié)點(diǎn)的遍歷來代替佳头，參考前序遍歷那一篇文章鹰贵。
不過為了體現(xiàn)圖的思想，這里都用上面這句代碼來實(shí)現(xiàn)吧康嘉。
- 1.利用隊(duì)列實(shí)現(xiàn)
- 2.從源節(jié)點(diǎn)開始依次按照寬度進(jìn)隊(duì)列碉输，然后彈出
- 3.每彈出一個(gè)節(jié)點(diǎn)，就把該節(jié)點(diǎn)所有沒有進(jìn)過隊(duì)列的鄰接點(diǎn)放入隊(duì)列
- 4.直到隊(duì)列變空
這里如果需要按照BFS的順序輸出二叉樹的元素的話亭珍，那么就可以把nodeSet去掉了敷钾。
def bfs(node):
if node is None:
return
queue = []
#nodeSet = set()
queue.insert(0,node)
#nodeSet.add(node)
while queue:
cur = queue.pop() # 彈出元素
print(cur.val) # 打印元素值
for next in cur.nexts: # 遍歷元素的鄰接節(jié)點(diǎn)
#if next not in nodeSet: # 若鄰接節(jié)點(diǎn)沒有入過隊(duì)，加入隊(duì)列并登記
#nodeSet.add(next)
queue.insert(0,next)
2.2肄梨、樹的深度優(yōu)先搜索
2.2.1阻荒、用遞歸的方法進(jìn)行dfs
這里遞歸不需要nodeSet
因?yàn)橄氲接袟５乃枷耄敲淳筒豢杀苊獾南氲竭f歸众羡。
- 遞歸結(jié)束條件：節(jié)點(diǎn)是None侨赡，結(jié)束函數(shù)調(diào)用
- 遞歸改變：每次都要把節(jié)點(diǎn)添加到節(jié)點(diǎn)集合當(dāng)中去
- 遞歸調(diào)用：對于每一個(gè)當(dāng)前節(jié)點(diǎn)的相鄰節(jié)點(diǎn)，只要不在節(jié)點(diǎn)集合中粱侣，就調(diào)用dfs進(jìn)行搜索
#nodeSet = set()
def dfs1(node):
if node is None:
return
#nodeSet.add(node)
print(node.val)
#相當(dāng)于樹的前序遍歷了羊壹，只不過這里把左右子節(jié)點(diǎn)放到了nexts的列表中
for next in node.nexts:
#if next not in nodeSet:
dfs1(next)
2.2.2、用循環(huán)的方法進(jìn)行dfs
這個(gè)方法其實(shí)是圖的遍歷方法齐婴，對于樹的DFS舶掖，其實(shí)不需要用nodeSet，可以參考樹3尔店，用循環(huán)實(shí)現(xiàn)樹的三種遍歷
若是按照如下方法進(jìn)行dfs，那么還是要用nodeSet來保證不會(huì)重復(fù)遍歷一些節(jié)點(diǎn)了主慰。
用循環(huán)的方法嚣州，就一定會(huì)用到棧了。
對于下面代碼共螺，有兩個(gè)地方需要解釋：
1该肴、為什么彈出了cur以后還要把cur壓入棧中？
答：為了保證出入棧的順序藐不，若是cur沒有子節(jié)點(diǎn)匀哄，則直接彈出棧。如果有子節(jié)點(diǎn)雏蛮，那么就要再把cur壓入棧涎嚼，再把cur的子節(jié)點(diǎn)壓入棧。這樣挑秉，下一次棧彈出的會(huì)是cur的子節(jié)點(diǎn)法梯，在子節(jié)點(diǎn)遍歷完并且再次彈出棧以后，當(dāng)前節(jié)點(diǎn)的索引又會(huì)回到父節(jié)點(diǎn)cur上。
2立哑、為什么最后要用break語句夜惭？
**保持深度優(yōu)先的順序，在遍歷完cur的左子節(jié)點(diǎn)以后铛绰，下一步會(huì)跳出循環(huán)诈茧，
- 你可以看看，若是不用break會(huì)是什么效果：以樹為例捂掰，在搜索完根節(jié)點(diǎn)的左子節(jié)點(diǎn)以后敢会，緊接著會(huì)把右子節(jié)點(diǎn)壓入棧中。而不是我們預(yù)想的把左子節(jié)點(diǎn)的左子節(jié)點(diǎn)壓入棧中尘颓。
- 在對root搜索到左子節(jié)點(diǎn)L1以后 走触，此時(shí)我們想對L1進(jìn)行搜索，而我們又想到此時(shí)此時(shí)此時(shí)疤苹，L1是在棧頂?shù)幕ス悖俏覀兒尾恢苯觔reak出循環(huán)，直接到對L1進(jìn)行搜索卧土。
所以循環(huán)中用了一個(gè)break來保持深度優(yōu)先
def dfs(node):
if node is None:
return
nodeSet = set()
stack = []
print(node.val)
nodeSet.add(node)
stack.append(node)
while len(stack) > 0:
cur = stack.pop() # 彈出最近入棧的節(jié)點(diǎn)
for next in cur.nexts: # 遍歷該節(jié)點(diǎn)的鄰接節(jié)點(diǎn)
if next not in nodeSet: # 如果鄰接節(jié)點(diǎn)不重復(fù)
stack.append(cur) # 把節(jié)點(diǎn)壓入
stack.append(next) # 把鄰接節(jié)點(diǎn)壓入
nodeSet.add(next) # 登記節(jié)點(diǎn)
print(next.val) # 打印節(jié)點(diǎn)值
break # 退出惫皱，保持深度優(yōu)先
用二叉樹來檢驗(yàn)上述算法
對于TreeNode類，在構(gòu)造函數(shù)中又添加了一個(gè)next屬性近似代替圖中的臨近節(jié)點(diǎn)列表尤莺。
#實(shí)現(xiàn)一個(gè)二叉樹旅敷，并且用BFS或DFS去遍歷她
class TreeNode:
def __init__(self,x):
self.val = x
self.left = None
self.right = None
self.nexts = []
root_node = TreeNode(1)
node_2 = TreeNode(2)
node_3 = TreeNode(3)
node_4 = TreeNode(4)
node_5 = TreeNode(5)
node_6 = TreeNode(6)
node_7 = TreeNode(7)
node_8 = TreeNode(8)
node_9 = TreeNode(9)
node_10 = TreeNode(10)
def littleTree(root,left,right):
root.left = left
root.right = right
if root.left:
root.nexts.append(root.left)
if root.right:
root.nexts.append(root.right)
littleTree(root_node, node_2, node_3)
littleTree(node_2, node_4, node_5)
littleTree(node_3, node_6, node_7)
littleTree(node_4, node_8, node_9)
littleTree(node_5, node_10, None)
