🔯從Python來學圖論Graph 與 DFS深度優先探索

NASA null on Unsplash

定義

圖Graph: 由節點和邊所組成的一個網狀資料結構。

圖的表達方式Graph representation:
常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。

本文以adjacenct list作為示範。

節點Vertex: 節點，也稱之為Node，圖的基本組成單元之一。

邊Edge: 邊，可分為有向邊Directed Edge，或無向邊Undirected Edge。

有向邊只能從起點走向終點。無向邊則可以雙向通過。

本文以有向邊作為示範。

深度優先拜訪DFS:
從某個指定的起點開始探索整張圖，只要找到某個相鄰的點還沒拜訪過，
就繼續遞迴拜訪下個對應的節點。

深度優先拜訪DFS

優點

1. 遞迴實現相對淺顯易懂。
2. 可以用來尋找指定的兩點之間是否有路徑存在。
3. 可以檢查Cycle環路是否存在。
4. 可以用來探索整張圖。

缺點

1. 遞迴實現需要維護額外的run time call stack遞迴堆疊的時間成本與空間成本。
2. 找到的路徑未必保證是最短路徑(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背後的本質

合縱連橫: 從路徑和 理解 DFS+樹型DP 框架的本質。

DFS+DP解情境模擬題: 走出邊界的方法數 Out of Boundary Paths_Leetcode #576

DFS經典應用題 BST最靠近的公共祖先節點 Leetcode #235

二元樹的拜訪 結合 DFS深度優先模板

使用DFS 模板 + 基礎圖論題目 Binary Tree Paths Leetcode #257

Graph theory圖論 DFS、BFS演算法的統整與比較