[Python] 實作 BFS (breadth-first search) 演算法
今天在解一個問題，發現需要用圖論中的 BFS 演算法來解～
問題類似下面這樣：每個 task 可能會有零到多個 sub-task，
而 sub-task 又可以再遞迴包含零到多個 sub-task…
但如果上層的 task 已經被標示成不需要跑的時候，希望子孫也都直接標成不要跑～
原本自己在實作時，一開始是像這麼寫的：
yielded_tasks_old_rounds = [] while task_list: yielded_tasks_cur_round = [] kept_tasks = [] for task in task_list: if not task.parent or task.parent in yielded_tasks_old_rounds: yielded_tasks_cur_round.append(task) yield task else: kept_tasks.append(task) yielded_tasks_old_rounds.extend(yielded_tasks_cur_round) task_list = kept_tasks
原本的想法是先走過一輪，把沒有父代的 task 找出來 yield 出去，
在下一輪的時候，把父代是已經被 yield 過的 task 找出來 yield 出去，
持續這種步驟直到 task_list 不再有 task 為止～
這個作法雖然算是 O(n)，但是有個嚴重的問題：假設 A, B 兩個 task 在同一層，
那麼 A 和 B 的直接的 children 應該要是 A 的先出現、再出現 B 的 children，
但上面的實作是照原本 task_list 的順序，所以雖然還是廣度優先，但在同一層看起來像是在亂跳…
重新研究了一下 BFS (breadth-first search)，原來應該是要將上層的 task 放在 queue 裡，
依序把他們的 children 放到 queue 的後面，再依序處理下去～
這個作法也是 O(n)，但確保了同一層中先出現的 task，其 children 在下一層也會先出現～
只是這個演算法會需要 parent->children 的關係，因此需要先建立起來，
不像我原本 (錯誤的) 實作是只需要原有的 child->parent 的關係：
dict_task_children = {} result_list = [] for task in task_list: if task.parent: # Construct a dict for mapping task->children tasks dict_task_children.setdefault(task.parent, []).append(task) else: # Initialize result list with tasks without parents in order result_list.append(task) i = 0 while i < len(result_list): task = result_list[i] yield task # Add children of current task at end of queue result_list.extend(dict_task_children.get(task, [])) i += 1
結論：蠻有趣的，不過我的演算法該重修了… Orz
參考資料：Graph Traversal: Breadth-first Search
(本頁面已被瀏覽過 988 次)