BFS演算法整理(python實作）
廣度優先演算法（Breadth-First-Search），簡稱BFS，是一種圖形搜索演算演算法，
1. 演算法的應用場景
2. 演算法的模板
2.1 針對樹的BFS模板
- 無需分層遍歷
from collections import deque
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def level_order_tree(root, result):
if not root:
return
# 這里借助python的雙向佇列實作佇列
# 避免使用list.pop(0)出站的時間復雜度為O(n)
queue = deque([root])
while queue:
node = queue.popleft()
# do somethings
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
if __name__ == "__main__":
tree = TreeNode(4)
tree.left = TreeNode(9)
tree.right = TreeNode(0)
tree.left.left = TreeNode(5)
tree.left.right = TreeNode(1)
print(level_order_tree(tree, []))
# [4, 9, 0, 5, 1]
- 需要分層遍歷
def level_order_tree(root):
if not root:
return
q = [root]
while q:
new_q = []
for node in q:
# do somethins with this layer nodes...
# 判斷左右子樹
if node.left:
new_q.append(node.left)
if node.right:
new_q.append(node.right)
# 記得將舊的佇列替換成新的佇列
q = new_q
# 最后return想要回傳的東西
return xxx
2.2 針對圖的BFS
- 無需分層遍歷的圖
from collections import deque
def bsf_graph(root):
if not root:
return
# queue和seen為一對好基友，同時出現
queue = deque([root])
# seen避免圖遍歷程序中重復訪問的情況，導致無法跳出回圈
seen = set([root])
while queue:
head = queue.popleft()
# do somethings with the head node
# 將head的鄰居都添加進來
for neighbor in head.neighbors:
if neighbor not in seen:
queue.append(neighbor)
seen.add(neighbor)
return xxx
- 需要分層遍歷的圖
def bsf_graph(root):
if not root:
return
queue = [root]
seen = set([root])
while queue:
new_queue = []
for node in queue:
# do somethins with the node
for neighbor in node.neighbors:
if neighbor not in seen:
new_queue.append(neighbor)
seen.add(neighbor)
return xxx
2.3 拓撲排序
在圖論中，由一個有向無環圖的頂點組成的序列，當且僅當滿足下列條件時，稱為該圖的一個拓撲排序（英語：Topological sorting），
每個頂點出現且只出現一次；
若A在序列中排在B的前面，則在圖中不存在從B到A的路徑，
實際應用
- 檢測編譯時的回圈依賴
- 制定有依賴關系的任務的執行順序（例如課程表問題）
演算法流程
- 統計所有點的入度，并初始化拓撲排序序列為空，
- 將所有入度為0的點，放到如BFS初始的搜索佇列中，
- 將佇列中的點一個一個釋放出來，把訪問其相鄰的點，并把這些點的入度-1.
- 如何發現某個點的入度為0時，則把這個點加入到佇列中，
- 當佇列為空時，回圈結束，
演算法實作
class Solution():
def top_sort(self, graph):
node_to_indegree = self.get_indegree(graph)
# 初始化拓撲排序序列為空
order = []
start_nodes = [node for node in graph if node_to_indegree[node] == 0]
queue = collection.deque(start_nodes)
while queue:
head = queue.popleft()
order.append(node)
for neighbor in head.neighbors:
node_to_indegree[neighbor] -= 1
if node_to_indegree[neighbor] == 0:
queue.append(neighbor)
return order
def get_indegree(self, graph):
node_to_indegree = {x: 0 for x in graph}
for node in graph:
for neighbor in node.neighbors:
node_to_indegree[neighbor] += 1
return node_to_indegree
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/137168.html
標籤：其他
上一篇：圖論篇4——拓撲排序