加入收藏 | 设为首页 |

感恩朋友-「Python | 边学边敲边记,附教程」第2次:深度&&广度优先算法

海外新闻 时间: 浏览:230 次



一、前语

今后尽量每天更新一篇,也是自己的一个学习打卡!加油!今日给咱们共享的是,Python里深度/广度优先算法介绍及完成。

二、深度、广度优先算法简介

1.深度优先查找(DepthFirstSearch)

深度优先查找的主要特征便是,假定一个极点有不少相邻极点,当咱们查找到该极点,咱们关于它的相邻极点感恩朋友-「Python | 边学边敲边记,附教程」第2次:深度&&广度优先算法并不是现在就对一切都进行查找,而是对一个极点持续往后查找,直到某个极点,他周围的相邻极点都现已被拜访过了,这时他就可以回来,对它来的那个极点的其他极点进行查找。

深度优先查找的完成可以运用递归很简单地完成。

2.广度优先查找(BreadthFirstSearch)

广度优先查找相关于深度优先查找侧重点不一样,深度优先好比是一个人走迷宫,一次只能选定一条路走下去,而广度优先查找好比是一次可以有恣意多个人,一次就走到和一个极点相连的一切未拜访过的极点,然后再从这些极点动身,持续这个进程。

详细完成的时分咱们运用先进先出行列来完成这个进程:

  1. 首先将起点参加行列,然后将其出队,把和起点相连的极点参加行列,
  2. 将队首元素v出队并符号他
  3. 将和v相连的未符号的元素参加行列,然后持续履行过程2直到行列为空

广度优先查找的一个重要作用便是它可以找出最短途径,这个很好了解,因为广度优先查找相当于每次从一个起点开端向一切或许的方向走一步,那么第一次抵达目的地的这个途径一定是最短的,而抵达了之后因为这个点现已被拜访过而不会再被拜访,这个途径就不会被更改了。

三、看代码,边学边敲边记深度优先、广度优先算法

1.遍历二叉树图形


遍历二叉树图形

2.深度优先、广度优先遍历感恩朋友-「Python | 边学边敲边记,附教程」第2次:深度&&广度优先算法模型

 1'''
2date : 2018.7.29
3author : 极简XksA
4goal : 深度/广度优先算法
5'''
6
7# 深度优先: 根左右 遍历
8# 广度优先: 层次遍历,一层一层遍历
9
10# 深度优先:感恩朋友-「Python | 边学边敲边记,附教程」第2次:深度&&广度优先算法 根左右 遍历 (递归完成)
11def 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# 广度优先: 层次遍历,一层一层遍历(行列完成)
20def 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(0) # 出行列
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) # 入行列

3.数据结构设计、遍历代码

办法一:列表法

 1# 树的数据结构设计
2# 1.列表法
3# 简述:列表里包括三个元素:根结点、左结点、右结点
4my_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# 深度优先: 根左右 遍历 (递归完成)
21def depth_tree(tree_node):
22 if tree_node:
23 print(tree_node[0])
24 # 拜访左子树
25 if tree_node[1]:
26 depth_tree(tree_node[1]) # 递归遍历
27 # 拜访右子树
28 if tree_node[2]:
29 depth_tree(tree_node[2]) # 递归遍历
30depth_tree(my_Tree)
31# result:
32# D B F G E C A H
33
34# 广度优先: 层次遍历,一层一层遍历(行列完成)
35def 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(0) # 出行列
43 print(node[0]) # 拜访结点
44 if node[1]:
45 my_queue.append(node[1]) # 入行列
46 if node[2]:
47 my_queue.append(node[2]) # 入行列
48level_queue(my_Tree)
49# result :
50# D B C F G A E H

办法二:结构类节点法

 1#2.结构类
2# Tree类,类变量root 为根结点,为str类型
3# 类变量ri阜新ght/left 为左右节点,为Tree型,默许为空
4class 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# 设置一切根结点
20a = Tree('A')
21b = Tree('B')
22c = Tree('C')
23d = Tree('D')
24e = Tree('E')
25f = Tree('F')
26g = Tree('G')
27h = Tree('H')
28# 设置节点之间联络,生成树
29a.left = h
30b.left = f
31b.right = g
32c.right = a
33d.left = b
34d.right = c
35g.left = e
36
37# 深度优先: 根左右 遍历 (递归完成)
38def 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) # 递归遍历
45depth_tree(d) # 传入根节点
46# result:
47# D B F G E C A H
48
49# 广度优先: 层次遍历,一层一层遍历(行列完成)
50def 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(0) # 出行列
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) # 入行列
63level_queue(d)
64# result :
65# D B C F G A E H

四、后言

或许咱们会猎奇,深度优先算法、广度优先算法对爬虫有什么用,不必猎奇,渐渐后边就会懂得了。提早泄漏:简直一切网站都有主页、XXX、XXX、XXX…在每个分页下,又有许多分页,这样一切url之间的联络实际上就可以比方成一棵树,当咱们想要体系爬取时,为了不重复爬取,对这颗树的遍历就尤为重要了,这儿提到的深度优先、广度优先为最常用的遍历算法。

边敲边学边做,坚持学习共享。

咱们直接私信小编“学习”就可以获取python从入门到通晓的教程了哦~~~~~