深度与广度优先搜索

深度优先搜索（Depth-First Search / DFS）

基本思想

深度优先搜索，从起点出发，从规定的方向中选择其中一个不断地向前走，直到无法继续为止，然后尝试另外一种方向，直到最后走到终点。就像走迷宫一样，尽量往深处走。
DFS 解决的是连通性的问题，即，给定两个点，一个是起始点，一个是终点，判断是不是有一条路径能从起点连接到终点。起点和终点，也可以指的是某种起始状态和最终的状态。问题的要求并不在乎路径是长还是短，只在乎有还是没有。有时候题目也会要求把找到的路径完整的打印出来。

广度优先搜索（Breadth-First Search / BFS）

基本思想

广度优先搜索，一般用来解决最短路径的问题。和深度优先搜索不同，广度优先的搜索是从起始点出发，一层一层地进行，每层当中的点距离起始点的步数都是相同的，当找到了目的地之后就可以立即结束。
广度优先的搜索可以同时从起始点和终点开始进行，称之为双端 BFS。这种算法往往可以大大地提高搜索的效率。

代码实现

假设我们有这么一个图，里面有A、B、C、D、E、F、G、H 8 个顶点，点和点之间的联系如下图所示，对这个图进行深度优先和广度优先的遍历。

from collections import deque

class Solution:
    def __init__(self):
        self.graph = {}
        self.graph['A'] = ['B','D','G']
        self.graph['B'] = ['A','E','F']
        self.graph['C'] = ['F','H']
        self.graph['D'] = ['A','F']
        self.graph['E'] = ['B','G']
        self.graph['F'] = ['B','C','D']
        self.graph['G'] = ['A','E']
        self.graph['H'] = ['C']
        
        self.done = {}
        self.done['A'] = 1
        self.done['B'] = 1
        self.done['C'] = 1
        self.done['D'] = 1
        self.done['E'] = 1
        self.done['F'] = 1
        self.done['G'] = 1
        self.done['H'] = 1
        
    def DFS(self):
        stack = []
        stack.append('A')
        self.done['A'] = 0
        print('已经访问过A！')
        
        while stack:
            t = 0
            for i in self.graph[stack[-1]]:
                t += self.done[i]
            if t == 0:
                stack.pop()
                continue
            
            for i in self.graph[stack[-1]]:
                if self.done[i]:
                    self.done[i] = 0
                    stack.append(i)
                    print('已经访问过'+i+'！')
                    print(stack)
                    break
        print('遍历完成')
    
    def BFS(self):
        queue = deque()
        queue.append('A')
        self.done['A'] = 0
        print('已经访问过A！')
        
        while queue:
            for i in self.graph[queue.popleft()]:
                if self.done[i]:
                    self.done[i] = 0
                    queue.append(i)
                    print('已经访问过'+i+'！')
                    print(queue)

            
if __name__ == '__main__':
    s = Solution()
    s.BFS()