廣度優(yōu)先搜索(breadth-first search)和深度優(yōu)先搜索(depth-first search)是兩種探索圖/樹中頂點的思路。這兩種搜索方式可以用來查找圖中某個指定的頂點，也可以用來對圖中頂點進行遍歷。

廣度優(yōu)先方式

廣度優(yōu)先遍歷圖的方式為，一次性訪問當(dāng)前頂點的所有未訪問狀態(tài)相鄰頂點，并依次對每個相鄰頂點執(zhí)行同樣處理。因為要依次對每個相鄰頂點執(zhí)行同樣的廣度優(yōu)先訪問操作，所以需要借助隊列結(jié)構(gòu)來存儲當(dāng)前頂點的相鄰頂點。

廣度優(yōu)先遍歷圖的方式，是以一種類似波紋擴散的方式進行的，不斷放大輻射半徑，進而覆蓋整張圖。

實現(xiàn)方式

1. 選擇起始頂點放入隊列，并標(biāo)記為已訪問；
2. 當(dāng)隊列不為空時，從隊列中取出頂點作為目標(biāo)頂點，將目標(biāo)頂點的所有相鄰且未被訪問過的頂點放入隊列，并標(biāo)記為已訪問；
3. 重復(fù)執(zhí)行步驟 2。

根據(jù)實現(xiàn)方式可知，廣度優(yōu)先遍歷的形式為，選擇目標(biāo)頂點后，依次訪問目標(biāo)頂點的所有相鄰頂點，再依次對每個相鄰頂點，依次訪問其相鄰頂點，如此重復(fù)對頂點執(zhí)行向外擴散的訪問操作，直至圖中所有頂點皆被訪問，即存儲頂點的隊列為空，表示已經(jīng)沒有未被訪問的頂點加入隊列。

示例演示

對于有向圖 digraph，圖的頂點集合和邊集合如下：

digraph

step 1:

選擇 3 作為起始頂點，此時：
隊列元素：3
已訪問元素：3

step 2:

頂點 3 出隊，將頂點 3 周圍未被訪問的頂點入隊：
隊列元素：1,5
已訪問元素：3,1,5

cycle 1:

頂點 5 出隊，將頂點 5 周圍未被訪問的頂點入隊：
隊列元素：1
已訪問元素：3,1,5

cycle 2:

頂點 1 出隊，將頂點 1 周圍未被訪問的頂點入隊：
隊列元素：2,4
已訪問元素：3,1,5,2,4

cycle 3:

頂點 4 出隊，將頂點 4 周圍未被訪問的頂點入隊：
隊列元素：2
已訪問元素：3,1,5,2,4

cycle 4:

頂點 2 出隊，將頂點 2 周圍未被訪問的頂點入隊：
隊列元素：
已訪問元素：3,1,5,2,4

參考代碼

def bfs(index, graph):
    queue, flag = Queue(), [False] * graph.number
    queue.put(index)  # save the node index
    flag[index - 1] = True  # indicates whether the node has been visited
    while not queue.empty():
        node = graph.list[queue.get() - 1]
        while node:
            if not flag[node.index - 1]:
                queue.put(node.index)
                flag[node.index - 1] = True
            node = node.next

程序中存在兩層循環(huán)，第一層循環(huán)為判斷存儲頂點的隊列是否為空，因為要對隊列中的每個頂點執(zhí)行訪問其相鄰頂點操作，所以若隊列不為空，則表示還有頂點的相鄰頂點未進行訪問。第二層循環(huán)為判斷相鄰頂點狀態(tài)，并執(zhí)行入隊操作。

性能分析

根據(jù)參考代碼和演示示例可知，對于圖中每個頂點的操作類型有如下幾種，入隊、出隊、設(shè)置已訪問狀態(tài)以及掃描頂點鄰接表。因為對于每個頂點以上操作只發(fā)生一次，所以入隊、出隊和已訪問狀態(tài)設(shè)置，時間復(fù)雜度為 ，根據(jù)鄰接表的介紹可知， 個頂點的鄰接表，存儲的總頂點個數(shù)為 或 ，所以廣度優(yōu)先遍歷的時間復(fù)雜度為 。bfs 算法過程中，需要申請 的數(shù)組記錄頂點的訪問狀態(tài)，需要申請 的隊列空間存儲頂點，且根據(jù)鄰接表的內(nèi)容可知，使用鄰接表作為存儲結(jié)構(gòu)的空間復(fù)雜度為 ，所以廣度優(yōu)先遍歷的空間復(fù)雜度為 。

深度優(yōu)先方式

深度優(yōu)先遍歷圖的方式，同樣會訪問一個頂點的所有相鄰頂點，不過深度優(yōu)先的方式為，首先訪問一個相鄰頂點，并繼續(xù)訪問該相鄰頂點的一個相鄰頂點，重復(fù)執(zhí)行直到當(dāng)前正在被訪問的頂點出度為零，或者不存在未訪問狀態(tài)的相鄰頂點，則回退到上一個頂點繼續(xù)按照該深度優(yōu)先方式訪問。因為存在回溯行為，所以需要借助棧結(jié)構(gòu)保存頂點，或者直接利用遞歸調(diào)用產(chǎn)生的方法棧幀來完成回溯。

相對于廣度優(yōu)先訪問，深度優(yōu)先的方式更像是一條路走到黑，走不下去了再回到上個路口選擇另外一條路。

實現(xiàn)方式

1. 選擇起始頂點入棧，并標(biāo)記為已訪問；
2. 當(dāng)棧不為空時，選擇棧頂元素作為目標(biāo)頂點，若目標(biāo)頂點存在未訪問狀態(tài)的相鄰頂點，則將該相鄰頂點入棧，并標(biāo)記為已訪問；若不存在未訪問狀態(tài)的相鄰頂點，則執(zhí)行出棧操作；
3. 重復(fù)執(zhí)行步驟 2。

示例演示

對于有向圖 digraph，圖的頂點集合和邊集合如下：

digraph

step 1:

選擇 3 作為起始頂點，此時：
棧元素：3
已訪問元素：3

step 2:

頂點 3 作為目標(biāo)頂點，將頂點 3 相鄰未訪問狀態(tài)的頂點入棧：
棧元素：3,5
已訪問元素：3,5

cycle 1:

頂點 5 作為目標(biāo)頂點，因為不存在相鄰未訪問狀態(tài)的頂點，所以執(zhí)行出棧操作：
棧元素：3
已訪問元素：3,5

cycle 2:

頂點 3 作為目標(biāo)頂點，將頂點 3 相鄰未訪問狀態(tài)的頂點入棧：
棧元素：3,1
已訪問元素：3,5,1

cycle 3:

頂點 1 作為目標(biāo)頂點，將頂點 1 相鄰未訪問狀態(tài)的頂點入棧：
棧元素：3,1,4
已訪問元素：3,5,1,4

cycle 4:

頂點 4 作為目標(biāo)頂點，因為不存在相鄰未訪問狀態(tài)的頂點，所以執(zhí)行出棧操作：
棧元素：3,1
已訪問元素：3,5,1,4

cycle 5:

頂點 1 作為目標(biāo)頂點，將頂點 1 相鄰未訪問狀態(tài)的頂點入棧：
棧元素：3,1,2
已訪問元素：3,5,1,4,2

cycle 6:

頂點 2 作為目標(biāo)頂點，因為不存在相鄰未訪問狀態(tài)的頂點，所以執(zhí)行出棧操作：
棧元素：3,1
已訪問元素：3,5,1,4,2

cycle 7:

頂點 1 作為目標(biāo)頂點，因為不存在相鄰未訪問狀態(tài)的頂點，所以執(zhí)行出棧操作：
棧元素：3
已訪問元素：3,5,1,4,2

cycle 8:

頂點 3 作為目標(biāo)頂點，因為不存在相鄰未訪問狀態(tài)的頂點，所以執(zhí)行出棧操作：
棧元素：
已訪問元素：3,5,1,4,2

參考代碼

def dfs(index, graph):
    stack, flag = [], [False] * graph.number
    stack.append(index)  # save the node index
    flag[index - 1] = True  # indicates whether the node has been visited
    while len(stack) > 0:
        node, size = graph.list[stack[-1] - 1], len(stack)
        while node:
            if not flag[node.index - 1]:
                stack.append(node.index)
                flag[node.index - 1] = True
                break
            node = node.next
        if size == len(stack):  # means no node append
            stack.pop()

程序中存在兩層循環(huán)，第一層循環(huán)為判斷棧是否為空，因為深度優(yōu)先的遍歷方式存在回溯的行為，所以借助棧結(jié)構(gòu)來完成回溯操作。當(dāng)棧為空時，表示已經(jīng)回溯到起始頂點，且沒有未訪問狀態(tài)的相鄰頂點入棧，即圖中所有頂點皆被訪問過。第二層循環(huán)為對目標(biāo)頂點的相鄰頂點進行掃描，若存在未訪問的相鄰頂點，則將該相鄰頂點入棧，并標(biāo)記為已訪問；若不存在，則執(zhí)行出棧操作。

這里提供另外一種實現(xiàn)方式，通過函數(shù)遞歸調(diào)用形成的方法棧幀完成回溯操作：

def dfs(index, graph, flag):
    node, flag[index - 1] = graph.list[index - 1], True
    while node:
        if not flag[node.index - 1]:
            dfs(node.index, graph, flag)
        node = node.next

性能分析

根據(jù)參考代碼和演示示例可知，對于圖中每個頂點的操作類型有如下幾種，入棧、出棧、設(shè)置已訪問狀態(tài)以及掃描頂點鄰接表。對于入棧、出棧以及設(shè)置訪問狀態(tài)操作，每個頂點只會執(zhí)行一次。根據(jù)程序中第二層循環(huán)的實現(xiàn)可知，對每個頂點的相鄰頂點掃描只會全掃描一次，掃描結(jié)束即發(fā)生回溯。所以深度優(yōu)先遍歷的時間復(fù)雜度為 。dfs 算法過程中，需要申請 的數(shù)組記錄頂點的訪問狀態(tài)，需要申請 的棧空間存儲頂點，且根據(jù)鄰接表的內(nèi)容可知，使用鄰接表作為存儲結(jié)構(gòu)的空間復(fù)雜度為 ，所以深度優(yōu)先遍歷的空間復(fù)雜度為 。

github 鏈接：廣度優(yōu)先與深度優(yōu)先