🔯從Python來學圖論Graph 與 BFS廣度優先探索

MJ Tangonan on Unsplash

定義

圖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)。

6. 可以根據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

合縱連橫: 從 圖論的應用題 理解BFS背後的本質

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