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