溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
以后盡量每天更新一篇，也是自己的一個學(xué)習(xí)打卡！加油！今天給大家分享的是，Python里深度/廣度優(yōu)先算法介紹及實現(xiàn)。
深度優(yōu)先搜索的主要特征就是，假設(shè)一個頂點有不少相鄰頂點，當(dāng)我們搜索到該頂點，我們對于它的相鄰頂點并不是現(xiàn)在就對所有都進行搜索，而是對一個頂點繼續(xù)往后搜索，直到某個頂點，他周圍的相鄰頂點都已經(jīng)被訪問過了，這時他就可以返回，對它來的那個頂點的其余頂點進行搜索。
深度優(yōu)先搜索的實現(xiàn)可以利用遞歸很簡單地實現(xiàn)。
廣度優(yōu)先搜索相對于深度優(yōu)先搜索側(cè)重點不一樣，深度優(yōu)先好比是一個人走迷宮，一次只能選定一條路走下去，而廣度優(yōu)先搜索好比是一次能夠有任意多個人，一次就走到和一個頂點相連的所有未訪問過的頂點，然后再從這些頂點出發(fā)，繼續(xù)這個過程。
具體實現(xiàn)的時候我們使用先進先出隊列來實現(xiàn)這個過程：
首先將起點加入隊列，然后將其出隊，把和起點相連的頂點加入隊列，
將隊首元素v出隊并標(biāo)記他
將和v相連的未標(biāo)記的元素加入隊列，然后繼續(xù)執(zhí)行步驟2直到隊列為空
廣度優(yōu)先搜索的一個重要作用就是它能夠找出最短路徑，這個很好理解，因為廣度優(yōu)先搜索相當(dāng)于每次從一個起點開始向所有可能的方向走一步，那么第一次到達目的地的這個路徑一定是最短的，而到達了之后由于這個點已經(jīng)被訪問過而不會再被訪問，這個路徑就不會被更改了。
1
'''
2
date : 2018.7.29
3
author : 極簡XksA
4
goal : 深度/廣度優(yōu)先算法
5
'''
6
7
# 深度優(yōu)先： 根左右 遍歷
8
# 廣度優(yōu)先： 層次遍歷，一層一層遍歷
9
10
# 深度優(yōu)先： 根左右 遍歷 (遞歸實現(xiàn))
11
def
depth_tree
(tree_node)
:
12
if
tree_node
is
not
None
:
13
print(tree_node._data)
14
if
tree_node._left
is
not
None
:
15
return
depth_tree(tree_node._left)
# 遞歸遍歷
16
if
tree_node._right
is
not
None
:
17
return
depth_tree(tree_node._right)
# 遞歸遍歷
18
19
# 廣度優(yōu)先： 層次遍歷，一層一層遍歷(隊列實現(xiàn))
20
def
level_queue
(root)
:
21
if
root
is
None
:
22
return
23
my_queue = []
24
node = root
25
my_queue.append(node)
# 根結(jié)點入隊列
26
while
my_queue:
27
node = my_queue.pop(
)
# 出隊列
28
print(node.elem)
# 訪問結(jié)點
29
if
node.lchild
is
not
None
:
30
my_queue.append(node.lchild)
# 入隊列
31
if
node.rchild
is
not
None
:
32
my_queue.append(node.rchild)
# 入隊列
方法一：列表法
1
# 樹的數(shù)據(jù)結(jié)構(gòu)設(shè)計
2
# 1.列表法
3
# 簡述：列表里包含三個元素：根結(jié)點、左結(jié)點、右結(jié)點
4
my_Tree = [
5
'D'
,
# 根結(jié)點
6
[
'B'
,
7
[
'F'
,[],[]],
8
[
'G'
,[
'E'
,[],[]],[]]
9
],
# 左子樹
10
[
'C'
,
11
[],
12
[
'A'
,[
'H'
,[],[]],[]]
13
]
# 右子樹
14
]
15
16
# 列表操作函數(shù)
17
# pop() 函數(shù)用于移除列表中的一個元素（默認(rèn)最后一個元素），并且返回該元素的值。
18
# insert() 函數(shù)用于將指定對象插入列表的指定位置,沒有返回值。
19
20
# 深度優(yōu)先： 根左右 遍歷 (遞歸實現(xiàn))
21
def
depth_tree
(tree_node)
:
22
if
tree_node:
23
print(tree_node[
])
24
# 訪問左子樹
25
if
tree_node[
1
]:
26
depth_tree(tree_node[
1
])
# 遞歸遍歷
27
# 訪問右子樹
28
if
tree_node[
2
]:
29
depth_tree(tree_node[
2
])
# 遞歸遍歷
30
depth_tree(my_Tree)
31
# result:
32
# D B F G E C A H
33
34
# 廣度優(yōu)先： 層次遍歷，一層一層遍歷(隊列實現(xiàn))
35
def
level_queue
(root)
:
36
if
not
root:
37
return
38
my_queue = []
39
node = root
40
my_queue.append(node)
# 根結(jié)點入隊列
41
while
my_queue:
42
node = my_queue.pop(
)
# 出隊列
43
print(node[
])
# 訪問結(jié)點
44
if
node[
1
]:
45
my_queue.append(node[
1
])
# 入隊列
46
if
node[
2
]:
47
my_queue.append(node[
2
])
# 入隊列
48
level_queue(my_Tree)
49
# result :
50
# D B C F G A E H
方法二：構(gòu)造類節(jié)點法
1
#2.構(gòu)造類
2
# Tree類，類變量root 為根結(jié)點，為str類型
3
# 類變量right/left 為左右節(jié)點，為Tree型，默認(rèn)為空
4
class
Tree
:
5
root =
''
6
right =
None
7
left =
None
8
# 初始化類
9
def
__init__
(self,node)
:
10
self.root = node
11
12
def
set_root
(self,node)
:
13
self.root = node
14
15
def
get_root
(self)
:
16
return
self.root
17
18
# 初始化樹
19
# 設(shè)置所有根結(jié)點
20
a = Tree(
'A'
)
21
b = Tree(
'B'
)
22
c = Tree(
'C'
)
23
d = Tree(
'D'
)
24
e = Tree(
'E'
)
25
f = Tree(
'F'
)
26
g = Tree(
'G'
)
27
h = Tree(
'H'
)
28
# 設(shè)置節(jié)點之間聯(lián)系，生成樹
29
a.left = h
30
b.left = f
31
b.right = g
32
c.right = a
33
d.left = b
34
d.right = c
35
g.left = e
36
37
# 深度優(yōu)先： 根左右 遍歷 (遞歸實現(xiàn))
38
def
depth_tree
(tree_node)
:
39
if
tree_node
is
not
None
:
40
print(tree_node.root)
41
if
tree_node.left
is
not
None
:
42
depth_tree(tree_node.left)
# 遞歸遍歷
43
if
tree_node.right
is
not
None
:
44
depth_tree(tree_node.right)
# 遞歸遍歷
45
depth_tree(d)
# 傳入根節(jié)點
46
# result:
47
# D B F G E C A H
48
49
# 廣度優(yōu)先： 層次遍歷，一層一層遍歷(隊列實現(xiàn))
50
def
level_queue
(root)
:
51
if
root
is
None
:
52
return
53
my_queue = []
54
node = root
55
my_queue.append(node)
# 根結(jié)點入隊列
56
while
my_queue:
57
node = my_queue.pop(
)
# 出隊列
58
print(node.root)
# 訪問結(jié)點
59
if
node.left
is
not
None
:
60
my_queue.append(node.left)
# 入隊列
61
if
node.right
is
not
None
:
62
my_queue.append(node.right)
# 入隊列
63
level_queue(d)
64
# result :
65
# D B C F G A E H
可能大家會好奇,深度優(yōu)先算法、廣度優(yōu)先算法對爬蟲有什么用，不用好奇，慢慢后面就會懂得了。提前透露：幾乎所有網(wǎng)站都有首頁、XXX、XXX、XXX…在每個分頁下，又有很多分頁，這樣所有url之間的聯(lián)系實際上就可以比喻成一棵樹，當(dāng)我們想要系統(tǒng)爬取時，為了不重復(fù)爬取，對這顆樹的遍歷就尤為重要了，這里說到的深度優(yōu)先、廣度優(yōu)先為最常用的遍歷算法。
邊敲邊學(xué)邊做，堅持學(xué)習(xí)分享。
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機網(wǎng)站二維碼