深度&&廣度優(yōu)先算法

深度&&廣度優(yōu)先算法

1．爬蟲(chóng)系列 深度&廣度優(yōu)先搜索 介紹

1.DFS（Depth-First-Search）深度優(yōu)先搜索，是計(jì)算機(jī)術(shù)語(yǔ)，是一種在開(kāi)發(fā)爬蟲(chóng)早期使用較多的方法，
是搜索算法的一種。它的目的是要達(dá)到被搜索結(jié)構(gòu)的葉結(jié)點(diǎn)(即那些不包含任何超鏈的HTML文件) 。
深度優(yōu)先搜索沿著HTML文件上的超鏈走到不能再深入為止，然后返回到這個(gè)HTML文件，再繼續(xù)選擇該HTML文件中的其他超鏈。
當(dāng)不再有其他超鏈可選擇時(shí)，說(shuō)明搜索已經(jīng)結(jié)束。
深度優(yōu)先搜索是一個(gè)遞歸的過(guò)程

2．深度優(yōu)先和廣度優(yōu)先搜索模型
廣度優(yōu)先搜索算法(Breadth First Search)，又稱為"寬度優(yōu)先搜索"或"橫向優(yōu)先搜索"，簡(jiǎn)稱BFS
理解了深度優(yōu)先搜索，也可以說(shuō)是縱向，而廣度優(yōu)先搜索可以理解為橫向同步搜索。初始點(diǎn)開(kāi)始后以層次的方式，從第一層的鄰接點(diǎn)開(kāi)始，從第一層的1節(jié)點(diǎn)到2節(jié)點(diǎn)等。然后第二層的3節(jié)點(diǎn)到4節(jié)點(diǎn)5節(jié)點(diǎn)再三層的5節(jié)點(diǎn)到6節(jié)點(diǎn)7節(jié)點(diǎn)8節(jié)點(diǎn)等。

圖：

# 深度優(yōu)先：根左右 遍歷
#廣度優(yōu)先： 層次遍歷，即一層一層遍歷

# 深度優(yōu)先：根左右 遍歷
def depth_tree(tree_node):
if tree_node is not None:
print(tree_node._data)
if tree_node._left is not None:
return depth_tree(tree_node._left) #遞歸遍歷
if tree_node._right is not None:
return depth_tree(tree_node._right) #遞歸遍歷

#廣度優(yōu)先： 層次遍歷，即一層一層遍歷
def level_queue(root):
if root is None:
return
my_queue=[]
node = root
my_queue.append(node) # 根結(jié)點(diǎn)入隊(duì)列
while my_queue:
node = my_queue.pop(0) # 出隊(duì)列
print(node.elem) # 訪問(wèn)結(jié)點(diǎn)
if node.lchild is not None:
my_queue.append(node.lchild) # 入隊(duì)列
if node.rchild is not None:
my_queue.append(node.rchild) # 入隊(duì)列

3.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、遍歷代碼
3.1列表法
根據(jù)樹(shù)形圖來(lái)實(shí)現(xiàn)
# 簡(jiǎn)述：列表里包含三個(gè)元素：根結(jié)點(diǎn)、左結(jié)點(diǎn)、右結(jié)點(diǎn)
my_Tree = [
'D', # 根結(jié)點(diǎn)
['B',
['F',[],[]],
['G',['E',[],[]],[]]
], # 左子樹(shù)
['C',
[],
['A',['H',[],[]],[]]
] # 右子樹(shù)
]

# 列表操作函數(shù)
#POP(0) 函數(shù)用于一處列表中的一個(gè)元素（默認(rèn)最后一個(gè)元素），并且返回該元素的值。
#insert（）函數(shù)用于將制定對(duì)象插入列表的制定位置，沒(méi)有返回值。

# 深度優(yōu)先： 根左右 遍歷 (遞歸實(shí)現(xiàn))

def depth_tree(tree_node):
if tree_node:
print(tree_node[0])
#訪問(wèn)左子樹(shù)
if tree_node[1]:
depth_tree(tree_node[1]) #遞歸遍歷
#訪問(wèn)右子樹(shù)
if tree_node[2]:
depth_tree(tree_node[2]) #遞歸遍歷
depth_tree(my_Tree)
執(zhí)行結(jié)果：為縱向搜索
D
B
F
G
E
C
A
H

廣度優(yōu)先： 層次遍歷，一層一層遍歷(隊(duì)列實(shí)現(xiàn))
def level_queue(root):
if not root:
return
my_queue = []
node = root
my_queue.append(node) # 根節(jié)點(diǎn)入隊(duì)列
while my_queue:
node = my_queue.pop(0) # 根節(jié)點(diǎn)出隊(duì)列
print(node[0]) #訪問(wèn)節(jié)點(diǎn)
if node[1]:
my_queue.append(node[1])
if node[2]:
my_queue.append(node[2])
level_queue(my_Tree)

執(zhí)行結(jié)果：結(jié)果為橫向搜索
D
B
C
F
G
A
E
H

3.2 構(gòu)建類節(jié)點(diǎn)法

# tree類，類變量root為根節(jié)點(diǎn)，為str類型
#類變量right/left 為左右節(jié)點(diǎn)，為tree型，默認(rèn)為空
class Tree:
root = ''
right = None
left = None
# 初始化類
def __init__(self,node):
self.root = node

def set_root(self,node):
self.root = node

def get_root(self):
return self.root
#初始化樹(shù)
#設(shè)置所有根節(jié)點(diǎn)
a = Tree('A')
b = Tree('B')
c = Tree('C')
d = Tree('D')
e = Tree('E')
f = Tree('F')
g = Tree('G')
h = Tree('H')
# 設(shè)置節(jié)點(diǎn)之間聯(lián)系，生成樹(shù)
a.left = h
b.left = f
b.right = g
c.right = a
d.left = b
d.right = c
g.left = e

#深度優(yōu)先：根左右 遍歷（遞歸實(shí)現(xiàn)）
def depth_tree(tree_node):
if tree_node is not None:
print(tree_node.root)
if tree_node.left is not None:
depth_tree(tree_node.left) # 遞歸遍歷
if tree_node.right is not None:
depth_tree(tree_node.right) # 遞歸遍歷
depth_tree(d) # 傳入根節(jié)點(diǎn)

執(zhí)行結(jié)果：
D
B
F
G
E
C
A
H

讀取順序

#廣度優(yōu)先：層次遍歷，一層一層遍歷（隊(duì)列實(shí)現(xiàn)）
def level_queue(root):
if root is None:
return
my_queue = []
node = root
my_queue.append(node)# 根節(jié)點(diǎn)入隊(duì)列
while my_queue:
node = my_queue.pop(0) #出隊(duì)列
print(node.root) #訪問(wèn)節(jié)點(diǎn)
if node.left is not None:
my_queue.append(node.left) #入隊(duì)列
if node.right is not None:
my_queue.append(node.right) #出隊(duì)列
level_queue(d)
#result:
結(jié)果：
D
B
C
F
G
A
E
H

讀取順序

做完深度優(yōu)先和廣度優(yōu)先策略算法后，返回來(lái)講，主要實(shí)現(xiàn)什么？
這兩種策略是爬蟲(chóng)系統(tǒng)抓取url的抓取策略，他們決定了爬取的url以什么樣的順序隊(duì)列進(jìn)行排列，深度優(yōu)先就是一條路走到黑，廣度優(yōu)先就是多條并發(fā)路線同時(shí)進(jìn)行排列。