【Python進階教學】BFS & DFS 廣度/深度優先搜尋【part-16】
===
目錄（Table of Contents）
[TOC]
---
哈囉大家好，很感謝你點進本文章，我是一名高中生，是電腦社社團的社長，由於我並不是 Python 這方面非常精通的專家，所以若文章有些錯誤請見諒，也可向我指正錯誤。另外本文章的用意是作為電腦社社團的教材使用而編寫的。
今天我們要講的演算法是鼎鼎大名、各位耳熟能詳的 BFS / DFS 廣度/深度優先演算法。那在深入 BFS / DFS 廣度/深度優先演算法之前呢，我們需要理解一下圖形理論的相關基礎知識，才能夠對 BFS / DFS 有更深入的了解。
接下來，讓我們進入正題（作者冒汗：因為這部份真的超難的）：
圖形理論（Graph Theory）
===
圖形理論簡稱圖論（Graph Theory），一個圖形可以由多個節點（node），或說頂點（vertice），跟連接節點的「邊線」組成，如下圖：
Image Source：[From left to right the underlying cycle graph, the associated graphs L... | Download Scientific Diagram](https://www.researchgate.net/figure/From-left-to-right-the-underlying-cycle-graph-the-associated-graphs-L-3-and-L-4_fig4_362229110)
圖：作者繪製
雖說上面的圖有點醜XD，但沒關係。其實像圖論的應用，我們可以用在平常大眾交通工具常見的路線圖（如：高雄輕軌路線圖、捷運路線圖等），還有在畫一些人際間的關係圖也很常用到這個圖論的部分。
至於一個頂點跟其他頂點有連線的話，那麼就稱為相鄰節點。如上圖所示，B、C 為相鄰節點，而 B、D 因為沒有直接相連，所以不是相鄰節點。
加權圖形（Weighted Graph）
---
> 權重（weight）：有時候我們會在每一個點和邊附帶一個數稱為「權重」。比較常見的是邊的權重（邊權），通常會作為表達長度或花費時間的方法。
圖：作者繪製
數字的定義需要由圖形代表的意義而定。（權重）數字可以是距離，也可以是所需金錢。
有向圖形（Directed Graph）
---
之前沒有加上箭頭的都是無向圖形（Undirected Graph），而有加上箭頭表明方向的就是有向圖形（Directed Graph），感覺好像在講幹話，但他的意思真的就是這樣XD，請同學自行回顧數學、物理所學的向量。
Image Source：[Directed graph - Wikipedia](https://en.wikipedia.org/wiki/Directed_graph)
有了方向以後，這個有向圖形就變得具有「順序性」，例如上圖中：如果我們的起點在 1，想要走到 4 的話，那是不是必須經過 3？因為如果我們進入到 2 的話就進入死胡同了，走不到 4，而 2 也沒有指向 4，所以要走 3。
而有向圖形不只是可以單向指向而已，也可以雙向指向，如上圖 3、4，可以聯想我們之前所學的鏈結串列。
有向無環圖（Directed Acyclic Graph：DAG）
---
圖：作者繪製
以上並不是一個有向無環圖（Not DAG），以下才是：
看出差別了嗎？有環跟無環的差別就在於有沒有形成一個「迴路（loop）」，無環圖就是斷了一截，使得只到某點就結束了。
而有向無環圖（DAG），指的是一個有向圖形，無法找到頂點能夠經過連接線回到該頂點，就叫 DAG。
什麼意思呢？用上面的 DAG 圖形解釋：
可以顯眼可見我們的起點在於 A，有兩條路可以走：B、C，如果走到 B 的話，就無法回到 A 了，因為這個方向只有去沒有回，B 旁邊周遭也沒有任何的連接線可以讓他走回去 A，那這就是無環圖。
拓樸排序（Topological Sort）
---
在圖論中，如果 DAG 每個頂點之間有順序性，就是拓樸排序（Topological Sort）。
廣度優先搜尋演算法（Breadth First Search：BFS）
===
廣度優先搜尋演算法（Breadth First Search：BFS），或稱寬度優先搜尋演算法，是電腦圖論中非常非常非常重要的搜尋演算法。
這個演算法簡單來說是一層一層的進行搜尋，如果搜尋完第一層後找不到，就繼續往上爬。而 BFS 會用到我們之前所學的佇列概念，主要是用於存放已搜尋跟待搜尋的資料，需要有先進先出的特性。
圖源：[【Day33】[演算法]-深度優先搜尋DFS與廣度優先搜尋BFS - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天](https://ithelp.ithome.com.tw/articles/10281404)
以上的圖我們由上往下解釋（我們要找的節點是 F）：
首先以 A 作為初始位置，可以看到 A 頂點「直接」連線的頂點（相鄰節點）有「B、D、E」。
好那這時候要做什麼呢？直接把 A 放入 Queue 中，然後再比對是否是 F，不是？那麼就移出 Queue。註：BFS 是一層一層搜尋，第一層只有一個頂點叫做 A。
接下來繼續，來到第二層，可以發現節點共有 B、D、E，將這三個放進去我們的佇列當中，先從最左邊的開始放。
由於 B 是先放進去的，且 Queue 的特性告訴我們它是 FIFO 先進先出的特性，所以 B 先比對，再來是 D、E。
比對完之後第二層的 B、D、E 以後，我們進入下一層：檢查 C、F 節點，首先我們檢查左邊的 C，比對是不是 F，不是？跳下一個，F 就是 F。
最短路徑
---
直接下結論：廣度優先搜尋演算法能夠尋找到最短路徑。
如果我們說 A - B 、 A - D 、 A - E 是一等連線，則廣度優先搜尋演算法就是先搜尋一等連線，如上一節解釋的那樣，如果在一等連線找不到，則往下找二等連線：
A - B - C 、 A - E - F
Python 實作：Collections 模組練習
---
實作之前，我們可以用一個模組叫 collections，以來方便進行佇列的相關運算：
append(x)：從右邊加入元素 x。
appendleft(x)：同上，從左邊加入。
pop()：移除右邊元素、回傳。
popleft()：移除左邊元素、回傳。
clear()：清除所有元素。
更多詳見：[collections --- 容器資料型態 — Python 3.12.3 說明文件](https://docs.python.org/zh-tw/3/library/collections.html)
首先我們來進行一些有關 collections 的練習：
```python=
from collections import deque
graph = {}
graph['A'] = ['B', 'D', 'E']
letter = deque()
letter += graph['A']
print(type(letter))
print(letter)
for i in range(len(letter)):
print(letter.popleft())
```
輸出結果：
```python=
<class 'collections.deque'>
deque(['B', 'D', 'E'])
B
D
E
```
說明：
第一行：從模組 collections 引入 deque 物件。
第三行：建立空字典
第四行：建立字典 graph，key = 'A'。
第五行：使用 deque() 物件建立 queue
第六行：將 graph['A'] 之鍵值加入佇列。
第七行：印出 letter 的型態（<class 'collections.deque'>）
第八行：印出 letter 的內容物（deque(['B', 'D', 'E'])）
第九～十行：for 迴圈依序迭代取出左邊元素並印出回傳值
同樣的程式碼，我們將 popleft() 改成 pop() 玩看看：
```python=
from collections import deque
graph = {}
graph['A'] = ['B', 'D', 'E']
letter = deque()
letter += graph['A']
print(type(letter))
print(letter)
for i in range(len(letter)):
print(letter.pop())
```
輸出結果：
```python=
<class 'collections.deque'>
deque(['B', 'D', 'E'])
E
D
B
```
可以發現 pop() 與 popleft() 的差別確實就是左邊跟右邊移出而已。
那麼我們利用以下範例程式碼來進行 append()、appendleft() 的練習：
```python=
from collections import deque
letter = deque()
letter.append('A')
letter.append('B')
print(letter)
letter.appendleft('C')
print(letter)
letter.appendleft('D')
print(letter)
```
輸出結果：
```python=
deque(['A', 'B'])
deque(['C', 'A', 'B'])
deque(['D', 'C', 'A', 'B'])
```
Python 實作：廣度優先搜尋演算法
---
使用 Python 進行廣度優先演算法的實作，我們使用字典（dict）這個資料型態會比較容易實作，同時也是很好去理解徒刑相鄰節點的方式。
```python=
from collections import deque
graph = {
'A' : ['B','D','E'],
'B' : ['A', 'C'],
'C' : ['B', 'E'],
'D' : ['A', 'E'],
'E' : ['A', 'D', 'F', 'C'],
'F' : ['E']
}
def BFS(graph, start):
queue = deque()
queue.append(start)
result = []
visited = set()
visited.add(start)
while (len(queue)>0):
currentVertex = queue.popleft()
result.append(currentVertex)
for neighbor in graph[currentVertex]:
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)
return result
print(BFS(graph, 'A')) # ['A', 'B', 'D', 'E', 'C', 'F']
print(BFS(graph, 'B')) # ['B', 'A', 'C', 'D', 'E', 'F']
print(BFS(graph, 'C')) # ['C', 'B', 'E', 'A', 'D', 'F']
```
範例出處：[【Day33】[演算法]-深度優先搜尋DFS與廣度優先搜尋BFS - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天](https://ithelp.ithome.com.tw/articles/10281404)
說明：
第二行～第九行：建立字典 graph，鍵分別為 'A' ~ 'F'，冒號右邊則為對應的鍵之值。其實建立這個就是有關於節點的直接連線啦，拿第一個 'A' 做解釋：右邊的值為 'B'、'D'、'E'，代表 'A' 直接跟 'B'、'D'、'E' 連線，稱作相鄰節點。
第十行：定義函數 BFS，參數為 graph、start，分別表示圖形與起始的節點。
第十一行：宣告變數 queue()，將其指定為 deque() 物件，表示建立一個佇列。（這邊用 list 也可以）
第十二行：將 start 值放入 queue 末端。
第十三行：宣告變數 result 為列表，表結果。
第十四行：宣告變數 visited，將其指定為 set()，表示建立一個空集合。表示將已經拜訪過的節點放入集合內。
第十五行：將 start 放入已拜訪的序列當中。
第十六行：while() 迴圈，條件為 len(queue) > 0 才會執行，代表說裡面的內容必須使 queue 長度減少至 0 才會結束迴圈。
第十七行：宣告 currentVertex 變數，表示當前節點，且指定為 queue.popleft()，將 queue 最左邊的元素移除，且回傳該元素值。如果是用 list 做法，popleft() 即 pop(0)。
第十八行：將 currentVertex 塞入 result 的末端。
第十九行：用 for 迴圈對 graph[currentVertex]（字典鍵裡面的值）所有相鄰節點進行迭代。
第二十行：如果相鄰節點尚未被訪問過，則......
第二十一～二十二行：將相鄰節點塞進去 queue 的末端，另外將這個相鄰節點新增在已拜訪的清單當中。
第二十三行：回傳結果。
以上程式碼是利用 BFS 廣度優先搜尋演算法進行拜訪所有節點的程式碼，這個程式碼還能夠再進行修改，比如說加入一個終止節點，表示只搜尋到某節點即結束：
```python=
from collections import deque
graph = {
'A' : ['B','D','E'],
'B' : ['A', 'C'],
'C' : ['B', 'E'],
'D' : ['A', 'E'],
'E' : ['A', 'D', 'F', 'C'],
'F' : ['E']
}
def BFS(graph, start, end):
queue = deque()
queue.append(start)
result = []
visited = set()
visited.add(start)
while (len(queue)>0):
currentVertex = queue.popleft()
result.append(currentVertex)
if currentVertex == end:
break
for neighbor in graph[currentVertex]:
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)
return result
print(BFS(graph, 'A', 'C')) # ['A', 'B', 'D', 'E', 'C']
```
以下是新增的部分：
```python=
if currentVertex == end:
break
```
Python 進階實作：利用廣度優先搜尋演算法走迷宮
---
以下範例是參考自書籍《演算法：圖解邏輯思維+ Python程式實作王者歸來》：
```python=
def is_exit(node):
if node == 'K':
return True
graph = {
'A' : ['B'],
'B' : ['A', 'C'],
'C' : ['B', 'D', 'E'],
'D' : ['C'],
'E' : ['C', 'H'],
'F' : ['G'],
'G' : ['F', 'H'],
'H' : ['E', 'G', 'I'],
'I' : ['H', 'K'],
'J' : ['G'],
'K' : ['I']
}
def bfs(graph, start):
visited = []
queue = [start]
while queue:
node = queue.pop(0)
if node not in visited:
visited.append(node)
neighbors = graph[node]
for n in neighbors:
queue.append(n)
if is_exit(node):
print(node, '是迷宮出口')
return visited
return visited
print(bfs(graph, 'A'))
```
可以看到這支程式碼，其實跟上面那個搜索所有節點的程式碼是一樣的，不過這邊將 collections 改成了 list 來進行存放，另外，輸出結果應該為：['A', 'B', 'C', 'D', 'E', 'H', 'G', 'I', 'F', 'J', 'K']，但實際上輸出結果少了 'J'、'K'，這部分同學可以從程式碼的先後順序去改變，至於 'J' 的部分，作者認為是原書《演算法：圖解邏輯思維+ Python程式實作王者歸來》作者範例程式碼上的圖形出現錯誤，我們只需要在圖形中的節點 'G' 後面的值加上 'J' 即可，不過要注意的是由於廣度優先是從左邊開始搜尋，因為正確的輸出結果，'J' 必須放置於 'F' 的後面。
所以經過修改以後，正確的程式碼如下：
```python=
def is_exit(node):
if node == 'K':
return True
graph = {
'A' : ['B'],
'B' : ['A', 'C'],
'C' : ['B', 'D', 'E'],
'D' : ['C'],
'E' : ['C', 'H'],
'F' : ['G'],
'G' : ['F', 'J', 'H'],
'H' : ['E', 'G', 'I'],
'I' : ['H', 'K'],
'J' : ['G'],
'K' : ['I']
}
def bfs(graph, start):
visited = []
queue = [start]
while queue:
node = queue.pop(0)
if node not in visited:
visited.append(node)
neighbors = graph[node]
for n in neighbors:
queue.append(n)
if is_exit(node):
print(node, '是迷宮出口')
return visited
return visited
print(bfs(graph, 'A'))
```
說明：
is_exit 函數部分，以 node 為參數，表節點，內部檢測 node 是否為 'K' 是的話回傳 True。
bfs 函數部分，共有兩參數，graph、start，分別為圖形與起始節點。
宣告 visited 局域變數，用於儲存已經被搜尋完畢的節點。
宣告 queue 局域變數，用於建立佇列，內部先存放 start，效果等同於 append()，但效率比他高。
進入無限迴圈（條件為 queue 為 True，即若 queue 裡面有東西的話就執行）：迴圈內部第一行宣告局域變數 node，用於紀錄從佇列最左邊移除的值。
接下來如果檢測 node 節點不在已搜尋清單的話，則將這個節點加入進去，並且將這個節點有的相鄰節點放入 neighbors 變數，之後以 for 迴圈遍歷 neighbors，將其放入待搜尋的佇列當中。
最後一個判斷式：判斷 is_exit(node) 是否為 True，是的話就印出 node 節點為出口，回傳已搜尋完畢的列表清單，中止函數。
深度優先搜尋演算法（Depth First Search：DFS）
===
深度優先搜尋演算法（Depth First Search），簡稱 DFS，指的是先深入一路徑當中搜尋，搜尋到末端以後發現若沒有找到指定目標，則回朔到前一層繼續搜尋。
與 BFS 相反的是，DFS 使用堆疊（stack）資料結構進行實作。
Image Source：[File:Depth-First-Search.gif - Wikipedia](https://en.m.wikipedia.org/wiki/File:Depth-First-Search.gif)
從 gif 圖中看到，DFS 同樣也是先從左邊的相鄰節點開始搜尋，DFS 是一次深入到底，不像 BFS 一次搜尋一層，之所以為什麼一個叫深度、一個叫廣度（寬度），原因於此。
那麼，我們預設這個搜尋會將所有節點「搜刮」完畢，那麼首先第一個節點 1 優先被放入堆疊內進行檢查，檢查完後，丟入已拜放列表 path。
接下來第二個節點 2，與節點 1 是同樣的步驟，接下來以此類推，從最左邊慢慢推到最右邊。
Python 實作
---
以下是一個範例，來源：書籍《演算法：圖解邏輯思維+ Python程式實作王者歸來》
```python=
def dfs(graph, start, goal):
path = []
stack = [start]
while stack:
node = stack.pop()
path.append(node)
if node == goal:
print('找到了')
return path
for n in graph[node]:
stack.append(n)
return "找不到"
graph = {
'A' : ['D', 'C', 'B'],
'B' : ['E'],
'C' : ['F'],
'D' : ['H', 'G'],
'E' : [],
'F' : ['J', 'I'],
'G' : [],
'H' : [],
'I' : [],
'J' : [],
}
print(dfs(graph, 'A', 'G')) # ['A', 'B', 'E', 'C', 'F', 'I', 'J', 'D', 'G']
```
說明：
path[] 為已拜訪過的節點。
這裡使用 pop() 而不是 pop(0)，是因為堆疊的特性為先進後出，要取出的話必須取出最後一個。
接下來是使用遞迴遍歷所有節點的程式碼（使用遞迴是因為遞迴有堆疊的特性）：
```python=
def dfs(graph, node, path=[]):
path += [node]
for n in graph[node]:
if n not in path:
path = dfs(graph, n, path)
return path
graph = {
'A' : ['B', 'C', 'D'],
'B' : ['A', 'E'],
'C' : ['A', 'F'],
'D' : ['A', 'G', 'H'],
'E' : ['B'],
'F' : ['C', 'I', 'J'],
'G' : ['D'],
'H' : ['D'],
'I' : ['F'],
'J' : ['F'],
}
print(dfs(graph, 'A')) # ['A', 'B', 'E', 'C', 'F', 'I', 'J', 'D', 'G', 'H']
```
可以看見遞迴的寫法程式碼會變得非常之簡潔，之前也說過，使用遞迴的方法雖然能讓程式碼簡潔易懂，但是缺點就是效率的問題。
這段程式碼還能夠再度修改成搜尋目標的形式，只是切記，在有遞迴的函數裡面是絕對不能寫搜尋指定節點的程式的，想知道為什麼，各位同學自己寫看看就知道了。
我的建議是可以再定義一個函數出來，然後在裡面將遞迴得到的結果拉出來進行判斷，就能達到這個目的了。
總結
===
圖形理論（graph theory）簡稱圖論，而一個圖由一個節點（node）或稱頂點（vertice），與邊線所組成。
平常大眾交通工具常見的路線圖（如：高雄輕軌路線圖、捷運路線圖等）、樹狀圖皆用到的是圖論的概念。
圖可以分為加權圖形（Weighted Graph），基本上就是在邊線上加上數字，這個數字可以由圖本身所具的意義去定義，如各個節點是車站，那麼邊線上的數字可能是坐到某某車站的距離或所需花費的金錢與時間。
有向圖形（Directed Graph）：邊線多了箭頭，指向某節點。
無向圖形（Undirected Graph）：沒箭頭的邊線。
有向無環圖（Directed Acyclic Graph：DAG）：沒有循環的有向圖形，簡單來說這種圖形有起始點跟終點，重要的是終點的部分，因為一個有循環的圖形沒有終點。
拓樸排序（Topological Sort）：在圖論中，如果 DAG 每個頂點之間有順序性，就是拓樸排序（Topological Sort）。
廣度優先搜尋演算法（Breadth First Search：BFS），或稱寬度優先搜尋演算法：一層一層進行搜尋，從左到右，因此實作上會用到 pop(0) 或（如果使用 collections 模組）用 deque() 建立一個佇列、popleft()、appendleft()。這種演算法主要在實作上運用的資料結構為佇列（queue）。
深度優先搜尋演算法（Depth First Search），簡稱 DFS，指的是先深入一路徑當中搜尋，搜尋到末端以後發現若沒有找到指定目標，則回朔到前一層繼續搜尋。關鍵字：深入到底、回朔到頭，代表這個演算法所主要使用的資料結構為堆疊（stack），在實作上可以使用列表模擬，也能直接使用遞迴還原原理。
| 屬性 | BFS | DFS |
| -------- | -------- | -------- |
| 搜尋策略 | 按層級逐層探索，先訪問所有同一層的節點再進入下一層 | 沿著一條路徑深入，直到達到終點或無法再深入為止 |
| 資料結構 | 佇列（Queue） | 堆疊（Stack）或遞迴 |
| 空間複雜度 | 較高，因為需要存儲所有同層的節點 | 較低，因為只需存儲當前路徑上的節點 |
| 時間複雜度 | O(V + E)，V 是節點數，E 是邊數 | O(V + E)，V 是節點數，E 是邊數 |
| 最短路徑 | 能夠找到從起點到終點的最短路徑 | 不一定能找到最短路徑 |
| 適用情況 | 適合尋找最短路徑，或需要找出所有可能解的情況 | 適合深度探索某些路徑或在需要探索所有可能解的情況 |
| 回溯性 | 不容易回溯 | 較容易回溯 |
| 應用 | 適用於廣泛的圖論演算問題，如最短路徑問題 | 適用於需要遍歷整個圖的問題，如拓撲排序、迷宮問題等 |
好啦，那以上就是今天教學的內容，以下是一些參考資料：
參考資料
===
書籍《演算法：圖解邏輯思維+ Python程式實作王者歸來》
[File:Depth-First-Search.gif - Wikipedia](https://en.m.wikipedia.org/wiki/File:Depth-First-Search.gif)
[Graph - 演算法筆記](https://web.ntnu.edu.tw/~algo/Graph2.html)
[From left to right the underlying cycle graph, the associated graphs L... | Download Scientific Diagram](https://www.researchgate.net/figure/From-left-to-right-the-underlying-cycle-graph-the-associated-graphs-L-3-and-L-4_fig4_362229110)
[4－基礎圖論 - HackMD](https://hackmd.io/@joylintp/2019_hsnu_training_4#1-%E4%BB%80%E9%BA%BC%E6%98%AF%E5%9C%96)
[Directed graph - Wikipedia](https://en.wikipedia.org/wiki/Directed_graph)
[【Day33】[演算法]-深度優先搜尋DFS與廣度優先搜尋BFS - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天](https://ithelp.ithome.com.tw/articles/10281404)
[廣度優先搜尋 - 維基百科，自由的百科全書](https://zh.wikipedia.org/zh-tw/%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2)
[collections --- 容器資料型態 — Python 3.12.3 說明文件](https://docs.python.org/zh-tw/3/library/collections.html)
Sign in with Wallet
Connect another wallet