深度优先与宽度优先搜索（python）

算法原理

1、宽度优先搜索：

宽度优先搜索算法(Breadth First Search，BSF)，思想是：

• 从图中某顶点v出发，首先访问顶点v
• 在访问了v之后依次从左往右访问v的各个未曾访问过的邻接点；
• 然后分别从这些邻接点出发依次从左往右访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问（C点优先于B的子节点）;
• 直至图中所有已被访问的顶点的邻接点都被访问到;
• 如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。
   
    换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路 径长度为1,2…的顶点。

如上图的BFS访问顺序为：A->B->C->D->E->F

2、深度优先搜索：

图的深度优先搜索(Depth First Search, DFS)，和树的前序遍历非常类似。

它的思想：

• 从顶点v出发，首先访问该顶点v;
• 然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图（B点的子节点孙节点…都优先于C点）;
• 直至图中所有和v有路径相通的顶点都被访问到。
• 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止

如上图的BFS访问顺序为：A->B->D->E->C->F

# -*- coding: utf-8 -*-
 
from collections import deque    # 线性表的模块
 
# 首先定义一个创建图的类，使用邻接矩阵
class Graph(object):
    def __init__(self, *args, **kwargs):
        self.order = []  # visited order
        self.neighbor = {}
 
    def add_node(self, node):
        key, val = node
        if not isinstance(val, list):
            print('节点输入时应该为一个线性表')    # 避免不正确的输入
        self.neighbor[key] = val
 
    # 宽度优先算法的实现
    def BFS(self, root):
        #首先判断根节点是否为空节点
        if root != None:
            search_queue = deque()
            search_queue.append(root)
            visited = []
        else:
            print('root is None')
            return -1
 
        while search_queue:
            # search_queue =[B,C] 
            person = search_queue.popleft()# B
            # search_queue =[C] 
            self.order.append(person)# [A, B]
 
            if (not person in visited) and (person in self.neighbor.keys()):
                # self.neighbor[person] = [D, E]
                # search_queue [C] 
                search_queue += self.neighbor[person]
                # search_queue [C, D, E] 从左往右宽度优先
                visited.append(person)
 
    # 深度优先算法的实现
    def DFS(self, root):
        # 首先判断根节点是否为空节点
        if root != None:
            search_queue = deque()
            search_queue.append(root)
 
            visited = []
        else:
            print('root is None')
            return -1
 
        while search_queue:
            # search_queue =[B,C] 
            person = search_queue.popleft()
            # search_queue=[C]
            self.order.append(person)
             # order = [A,B]
            if (not person in visited) and (person in self.neighbor.keys()):
                tmp = self.neighbor[person]#[D, E]
                tmp.reverse()# tmp 因为下面打算左添加
                 # search_queue=[C] # 左边添加 tmp
                for index in tmp:
                    search_queue.appendleft(index)
                # search_queue =[D,E,C] 从左下到右，深度优先
 
                visited.append(person)# visited= [A, B]
 
    def clear(self):
        self.order = []
 
    def node_print(self):
        for index in self.order:
            print(index, end='  ')
 
 
if __name__ == '__main__':
    # 创建一个二叉树图
    g = Graph()
    g.add_node(('A', ['B', 'C']))
    g.add_node(('B', ['D', 'E']))
    g.add_node(('C', ['F']))
 
    # 进行宽度优先搜索
    g.BFS('A')
    print('宽度优先搜索:')
    print('  ', end='  ')
    g.node_print()
    g.clear()
 
    # 进行深度优先搜索
    print('\n\n深度优先搜索:')
    print('  ', end='  ')
    g.DFS('A')
    g.node_print()
    print()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

运行结果：