定義
圖Graph: 由節點和邊所組成的一個網狀資料結構。
常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。
本文以adjacenct list作為示範。
節點Vertex: 節點，也稱之為Node，圖的基本組成單元之一。
邊Edge: 邊，可分為有向邊Directed Edge，或無向邊Undirected Edge。
有向邊只能從起點走向終點。無向邊則可以雙向通過。
本文以有向邊作為示範。
廣度優先拜訪BFS:
從某個指定的起點開始探索整張圖，由內而外，逐層拜訪所有相鄰的節點。
比喻:
就好像一個小石頭(或小水滴)掉入水中，同心圓往外一層一層水波紋擴散的模式。
等權圖 Equal weighted Graph
圖中所有的邊的成本都相同，最常見的簡化版本是每條邊的成本都為1。
最短路徑 Shortest Path:
從起點出發，走到終點的最短路徑(或最小成本)。
當圖Graph是Edge成本都為1的等權圖的時候，
最短路徑 = 最佳路徑上經過的Edge總數。
範例 等權圖中 A→D 的最短路徑
演算法 用BFS來找等權圖中的最短路徑
1.建造一個BFS_queue，初始化時，放入起點和計步器(一開始歸零)。
2.遵循BFS演算法，從BFS_queue取出下一個要拜訪的節點和計步器的值。
3.由內而外逐層探索鄰居，並且將鄰居節點和計步器+1的值推入BFS_queue。
4.假如某一步發現現在的節點就是終點，則輸出成功訊息，並且把最短路徑的長度輸出。
- 假如整張圖都拜訪完還是走不到終點，則輸出失敗訊息，提示無法從起點走到終點。
演算法的時間複雜度 O(V+E) 每個點至多拜訪一次，每條邊最多檢查一次。
詳細圖解 等權圖BFS最短路徑範例
最短路徑程式碼(底層依賴BFS廣度優先探索演算法)
def shortest_path(self, start_node, target, visited=None):
if visited is None:
visited = set()
bfs_queue = deque([(start_node, 0)])
visited.add(start_node)
while bfs_queue:
cur, step = bfs_queue.popleft()
if cur == target:
print(f"shortest path from {start_node.value} to {target.value} takes {step} steps.")
return
print(cur.value)
for edge in cur.edges:
if edge.to_node not in visited:
visited.add(edge.to_node)
bfs_queue.append( (edge.to_node, step+1) )
print(f"There is no shortest path from {start_node.value} to {target.value}.")
return
體驗BFS廣度優先搜尋 與 等權圖最短路經的關聯
完整的等權圖BFS 廣度優先拜訪與最短路徑實作和程式碼
from collections import deque
class Node:
def __init__(self, value):
self.value = value
self.edges = []
def add_edge(self, edge):
self.edges.append(edge)
class Edge:
def __init__(self, from_node, to_node):
self.from_node = from_node
self.to_node = to_node
class Graph:
def __init__(self):
self.nodes = []
def add_node(self, node):
self.nodes.append(node)
def add_edge(self, from_node, to_node):
edge = Edge(from_node, to_node)
from_node.add_edge(edge)
def dfs(self, start_node, visited=None):
if visited is None:
visited = set()
visited.add(start_node)
print(start_node.value)
for edge in start_node.edges:
if edge.to_node not in visited:
self.dfs(edge.to_node, visited)
def shortest_path(self, start_node, target, visited=None):
if visited is None:
visited = set()
bfs_queue = deque([(start_node, 0)])
visited.add(start_node)
while bfs_queue:
cur, step = bfs_queue.popleft()
if cur == target:
print(f"shortest path from {start_node.value} to {target.value} takes {step} steps.")
return
print(cur.value)
for edge in cur.edges:
if edge.to_node not in visited:
visited.add(edge.to_node)
bfs_queue.append( (edge.to_node, step+1) )
print(f"There is no shortest path from {start_node.value} to {target.value}.")
return
def demo():
# Graph and BFS demo
# Create Graph
graph = Graph()
# Create Node
nodeA = Node('A')
nodeB = Node('B')
nodeC = Node('C')
nodeD = Node('D')
nodeE = Node('E')
nodeF = Node('F')
# Add node into Graph
graph.add_node(nodeA)
graph.add_node(nodeB)
graph.add_node(nodeC)
graph.add_node(nodeD)
graph.add_node(nodeE)
graph.add_node(nodeF)
# Add edge into Graph
graph.add_edge(nodeA, nodeB)
graph.add_edge(nodeA, nodeC)
graph.add_edge(nodeB, nodeD)
graph.add_edge(nodeB, nodeE)
graph.add_edge(nodeC, nodeF)
graph.add_edge(nodeF, nodeD)
print("BFS traversal starting from node A:")
# 嘗試尋找從A走到D的最短路徑
graph.shortest_path(nodeA, nodeD)
# 嘗試尋找從C走到A的最短路徑
#graph.shortest_path(nodeC, nodeA)
if __name__ == '__main__':
demo()
測試輸出
BFS traversal starting from node A:
A
B
C
shortest path from A to D takes 2 steps.
結語
其實BFS廣度優先演算法就相當於水波紋從波源開始擴散的過程模擬。
當輸入是等權圖時，就可以利用這項特質，透過BFS來找從起點走到終點的最短路徑。
最短路徑(最小成本) = 水波紋擴散層數 = 從起點到終點 沿路經過的Edge總數
讀者可以透過紙筆追蹤演算法和程式執行邏輯，測試幾個簡單的小範例，
會有更深刻的了解和體會！
Graph圖論BFS相關的演算法練習題與詳解
BFS 經典入門題 Binary Tree Level Order Traversal_Leetcode #102
BFS 經典入門題 Binary Tree Level Order Traversal II Leetcode #107
BFS應用題 Find Largest Value in Each Tree Row Leetcode #515
BFS經典應用 最精簡公車路線搭乘次數 Bus Routes_Leetcode #815
一魚多吃 用BFS來列出拜訪路徑 Diagonal Traverse II_Leetcode#1424
一題多解 用DP、BFS去解 Pefect Square 完全平方數的化簡_Leetcode #279