深度優(yōu)先搜索（Depth-First Search / DFS）

基本思想

深度優(yōu)先搜索，從起點(diǎn)出發(fā)，從規(guī)定的方向中選擇其中一個(gè)不斷地向前走，直到無(wú)法繼續(xù)為止，然后嘗試另外一種方向，直到最后走到終點(diǎn)。就像走迷宮一樣，盡量往深處走。
DFS 解決的是連通性的問(wèn)題，即，給定兩個(gè)點(diǎn)，一個(gè)是起始點(diǎn)，一個(gè)是終點(diǎn)，判斷是不是有一條路徑能從起點(diǎn)連接到終點(diǎn)。起點(diǎn)和終點(diǎn)，也可以指的是某種起始狀態(tài)和最終的狀態(tài)。問(wèn)題的要求并不在乎路徑是長(zhǎng)還是短，只在乎有還是沒(méi)有。有時(shí)候題目也會(huì)要求把找到的路徑完整的打印出來(lái)。

廣度優(yōu)先搜索（Breadth-First Search / BFS）

基本思想

廣度優(yōu)先搜索，一般用來(lái)解決最短路徑的問(wèn)題。和深度優(yōu)先搜索不同，廣度優(yōu)先的搜索是從起始點(diǎn)出發(fā)，一層一層地進(jìn)行，每層當(dāng)中的點(diǎn)距離起始點(diǎn)的步數(shù)都是相同的，當(dāng)找到了目的地之后就可以立即結(jié)束。
廣度優(yōu)先的搜索可以同時(shí)從起始點(diǎn)和終點(diǎn)開(kāi)始進(jìn)行，稱之為雙端 BFS。這種算法往往可以大大地提高搜索的效率。

代碼實(shí)現(xiàn)

假設(shè)我們有這么一個(gè)圖，里面有A、B、C、D、E、F、G、H 8 個(gè)頂點(diǎn)，點(diǎn)和點(diǎn)之間的聯(lián)系如下圖所示，對(duì)這個(gè)圖進(jìn)行深度優(yōu)先和廣度優(yōu)先的遍歷。

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('已經(jīng)訪問(wèn)過(guò)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('已經(jīng)訪問(wèn)過(guò)'+i+'！')
                    print(stack)
                    break
        print('遍歷完成')
    
    def BFS(self):
        queue = deque()
        queue.append('A')
        self.done['A'] = 0
        print('已經(jīng)訪問(wèn)過(guò)A！')
        
        while queue:
            for i in self.graph[queue.popleft()]:
                if self.done[i]:
                    self.done[i] = 0
                    queue.append(i)
                    print('已經(jīng)訪問(wèn)過(guò)'+i+'！')
                    print(queue)

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