🔯從Python來學圖論Graph 與 DFS深度優先探索
定義
圖Graph: 由節點和邊所組成的一個網狀資料結構。
圖的表達方式Graph representation:
常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。
本文以adjacenct list作為示範。
節點Vertex: 節點，也稱之為Node，圖的基本組成單元之一。
邊Edge: 邊，可分為有向邊Directed Edge，或無向邊Undirected Edge。
有向邊只能從起點走向終點。無向邊則可以雙向通過。
本文以有向邊作為示範。
深度優先拜訪DFS:
從某個指定的起點開始探索整張圖，只要找到某個相鄰的點還沒拜訪過，
就繼續遞迴拜訪下個對應的節點。
深度優先拜訪DFS
優點
- 遞迴實現相對淺顯易懂。
- 可以用來尋找指定的兩點之間是否有路徑存在。
- 可以檢查Cycle環路是否存在。
- 可以用來探索整張圖。
缺點
- 遞迴實現需要維護額外的run time call stack遞迴堆疊的時間成本與空間成本。
- 找到的路徑未必保證是最短路徑(Not shortest path always)。
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 dfs(self, start_node, visited=None):
if visited is None:
visited = set()
# 標記為已拜訪
visited.add(start_node)
print(start_node.value)
# DFS 遞迴拜訪下一個相鄰的節點
for edge in start_node.edges:
if edge.to_node not in visited:
self.dfs(edge.to_node, visited)
測試範例
完整的Graph 與 DFS 深度優先拜訪實作和程式碼
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 demo():
# Graph and DFS 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)
# 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("DFS traversal starting from node A:")
graph.dfs(nodeA)
if __name__ == '__main__':
demo()
測試輸出
DFS traversal starting from node A:
A
B
D
E
C
結語
其實Graph就是Node的組合與推廣，每個節點可以和數個不同的相鄰節點有邊相連。
特化成鍊狀的Graph就是Linked List。
特化成樹狀的Graph就是Tree, Binary Tree, Binary Search Tree, AVL Tree, ... 等等。
讀者可以透過紙筆追蹤演算法和程式執行邏輯，測試幾個簡單的小範例，
會有更深刻的了解和體會！
Graph圖論DFS相關的演算法練習題與詳解
🎄圖論應用: 二元樹的中序拜訪 Binary Tree Inorder Traversal_LC #94
🎄圖論應用: 二元樹的後序拜訪 Binary Tree Postorder Traversal_LC #145
🎄圖論應用: 樹的後序拜訪 N-ary Tree Postorder Traversal_Leetcode #590
尋寶之旅 挖掘最多金礦的走法 (DFS+最佳化)Leetcode #1219
DFS應用: 在二元樹插入新的一層 Add one row to Tree_Leetcode #623
DFS+DP解情境模擬題: 走出邊界的方法數 Out of Boundary Paths_Leetcode #576
DFS經典應用題 BST最靠近的公共祖先節點 Leetcode #235
使用DFS 模板 + 基礎圖論題目 Binary Tree Paths Leetcode #257
你可能也想看
