---
tags: Python語法筆記
---

# Pyhton的 BFS 實作－queue的選擇

請搭配影片服用 [Python APCS 題解：血緣關係(AP201603_4)](https://www.youtube.com/watch?v=WVLEUoR-uT8&list=PLpmg1QLbgMuRQXHRkX9iDHyAVIW1D6OJF&index=2)

影片中提到樹的題目如果用遞迴 Top Down的解法可能會有深度過深的風險
因此建議學習Python者遇到樹dp問題還是要學習利用 queue 做類似 bfs 的Bottom Up解法
影片中實作 bfs 時用 `list` 實作 queue，本文將提供其他選項並討論各自優缺點

## 以 `list` 實作

影片中使用的方法，應該也是對新手最友善的方式，不須多背一個物件的用法。
但要特別注意的是不可使用 `que.pop(0)` ，因為這是 $O(n)$ 的操作。

影片中示範的是利用一個 front 紀錄維護位置，其實也可以搭配 `for` 迴圈完成(見範例程式碼)，看起來稍微簡潔一些。

這種方式的缺點是稍微浪費記憶體，畢竟用完的點沒有清理掉，但大部分的樹或圖的bfs問題只要把所有點放進去一次，所以list的總長度不會超過節點數量，在APCS的題目都不至於造成記憶體錯誤。
- 優點：不用多背函式的語法，效率高。
- 缺點：記憶體占用，僅適合解題；乍看之下看不出來是queue。

que = [v for v in range(n) if deg[v] == 0]
for v in q:
    p = parent[v]
    if p < 0: break
    #do_something

    deg[p] -= 1
    if deg[p]: que.append(p)

## Python 的 `Queue`

看起來是最正統的方法，但也是效率最差的方法。
因為Python的Queue主要用於多執行緒的 synconization

- 優點：正統、省記憶體（可將用完的節點刪除）
- 缺點：慢！有夠慢！（在judge上實測同樣演算法大概比其他兩者慢2倍）

from queue import Queue
q = Queue()            #宣告一個空的queue
q.put(5)               #放入一個數字
a = q.get()            #取出一個數字，空的時候會一直等到有人put為止
b = q.get_nowait()     #取出一個數字，空的時候會直接error
q.qsize()              #回傳queue目前的大小
q.empty()              #回傳queue是否為空

bfs 的模板大致如下

from queue import Queue
que = Queue()
for v in range(n):
    if deg[v] == 0:
        que.put_nowait()
while not q.empty():
    p = parent[v]
    if p < 0: break
    #do_something

    deg[p] -= 1
    if deg[p]: que.append(p)

## 用 `deque` 實作

Python裡面的 deque 可以做到在 $O(1)$ 時間內從左側或右側新增/刪除。常用語法如下：

from collections import deque #兩者擇一即可 
from queue import deque       #兩者擇一即可 

dq = deque() #宣告一個同白的deque
dq = deque([1,2,3,4,5]) #將一個list轉換成deque

dq.append(6)             #新增在最後面
dq.appendleft(0)         #新增在最前面
rear = dq.pop()          #從最後面拔除一個，並將值回傳
front = dq.popleft()     #從最前面拔除一個，並將值回傳

l = len(dq)              #取得dq的長度

所以我們可以用 deque ，然後只用 `append`(加在右側) 跟 `popleft`(從左側刪除) 就可以當成 queue 來使用了。聽起來好像殺雞用牛刀，但是因為 python 中的 deque 沒有syncronization 的問題，效能比 queue 高出一倍！

- 優點：省記憶體（可將用完的節點刪除）、效率高。
- 缺點：需要多背deque相關函式的語法

#from collections import deque 
from queue import deque

que = deque([v for v in range(n) if deg[v] == 0])

while len(que)>0:
    v = que.popleft()
    p = parent[v]
    if p < 0: break
    #do_something
    
    deg[p] -= 1
    if deg[p] == 0:
        que.append(p)