定義
圖Graph: 由節點和邊所組成的一個網狀資料結構。
圖的表達方式Graph representation:
常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。
本文以adjacenct list作為示範。
節點Vertex: 節點，也稱之為Node，圖的基本組成單元之一。
邊Edge: 邊，可分為有向邊Directed Edge，或無向邊Undirected Edge。
有向邊只能從起點走向終點。無向邊則可以雙向通過。
本文以有向邊作為示範。
廣度優先拜訪BFS:
從某個指定的起點開始探索整張圖，由內而外，逐層拜訪所有相鄰的節點。
比喻:
就好像一個小石頭丟入水中，同心圓往外一層一層水波紋擴散的模式。
廣度優先拜訪BFS
優點
1.底層依賴Queue，能維護First in First out，先看到先拜訪的這項性質。
2.可以用來尋找指定的兩點之間是否有路徑存在。
3.可以檢查Cycle環路是否存在。
4.可以用來探索整張圖。
5.當邊權種相等時，找到的路徑保證是最短路徑(Shortest Path)。
- 可以根據degree來進行拓樸排序Topological Sort，
解決任務優先順序相關的問題。
缺點
1.當只需要檢查路徑存在時，會耗費許多不必要的搜索時間。
Graph的Class定義與建構子
class Graph:
def __init__(self):
# 節點清單
self.nodes = []
Node的Class定義
class Node:
def __init__(self, value):
# 節點值
self.value = value
# Edge list
self.edges = []
def add_edge(self, edge):
# 節點加入一條相連的有向邊
self.edges.append(edge)
Edge的Class定義
class Edge:
def __init__(self, from_node, to_node):
# 起點
self.from_node = from_node
# 終點
self.to_node = to_node
Graph常見的操作
1.增加一個節點
在圖中新增一個節點，並且放入Graph圖裡的節點清單self.nodes。
時間複雜度 O(1)
def add_node(self, node):
self.nodes.append(node)
2.增加一條邊
在圖中新增一條邊，並且把這條邊放入起點的edge list。
時間複雜度 O(1)
def add_edge(self, from_node, to_node):
# 根據(起點,終點) 建立一條邊
edge = Edge(from_node, to_node)
# 起點加入新的一條邊
from_node.add_edge(edge)
3.廣度優先拜訪
從某個指定的起點開始探索整張圖，由內而外，逐層拜訪所有相鄰的節點。
時間複雜度 O(V+E) 每個點至多拜訪一次，每條邊最多檢查一次。
def bfs(self, start_node, visited=None):
if visited is None:
visited = set()
bfs_queue = deque([start_node])
visited.add(start_node)
while bfs_queue:
cur = bfs_queue.popleft()
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)
return
測試範例
完整的Graph 與 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 bfs(self, start_node, visited=None):
if visited is None:
visited = set()
bfs_queue = deque([start_node])
visited.add(start_node)
while bfs_queue:
cur = bfs_queue.popleft()
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)
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')
# Add node into Graph
graph.add_node(nodeA)
graph.add_node(nodeB)
graph.add_node(nodeC)
graph.add_node(nodeD)
graph.add_node(nodeE)
# 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, nodeD)
print("BFS traversal starting from node A:")
graph.bfs(nodeA)
if __name__ == '__main__':
demo()
測試輸出
BFS traversal starting from node A:
A
B
C
D
E
結語
其實Graph就是Node的組合與推廣，每個節點可以和數個不同的相鄰節點有邊相連。
特化成鍊狀的Graph就是Linked List。
特化成樹狀的Graph就是Tree, Binary Tree, Binary Search Tree, AVL Tree, ... 等等。
讀者可以透過紙筆追蹤演算法和程式執行邏輯，測試幾個簡單的小範例，
會有更深刻的了解和體會！
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
