Python 資料結構實戰：堆積積、樹與圖的應用

在 Python 開發中，資料結構的運用至關重要，尤其堆積積、樹和圖更是解決許多複雜問題的利器。heapq 模組提供便捷的堆積積操作方式，能有效管理優先佇列。樹狀結構則適用於表示階層式資料，例如檔案系統或組織架構。圖結構則更擅長於描繪物件之間的關係，常見於社交網路分析、地圖導航等應用。理解這些資料結構的特性和操作方法，能提升程式碼的效率和可讀性。透過 Python 的物件導向特性，可以輕鬆建立和操作這些資料結構，例如利用類別定義節點，並使用列表或集合表示節點間的關係。在圖形結構中，深度優先搜尋（DFS）和廣度優先搜尋（BFS）是兩種常用的遍歷演算法，選擇哪種演算法取決於具體的應用場景。例如，DFS 適合用於尋找特定路徑，而 BFS 則更適合用於尋找最短路徑。

駕馭資料結構：堆積積、樹與圖的 Python 實戰

資料結構是程式設計的根本，掌握它們能讓你在解決複雜問題時更加得心應手。今天，玄貓將帶領大家探討 Python 中三種重要的資料結構：堆積積（Heap）、樹（Tree）和圖（Graph），並結合實際範例，讓你輕鬆掌握它們的應用。

堆積積 (Heap)：高效管理優先順序任務

堆積積是一種特殊的樹狀資料結構，最常見的應用就是優先佇列。在 Python 中，heapq 模組提供了堆積積的實作，讓我們可以輕鬆地建立和操作堆積積。

建立堆積積

heapq 模組提供 heapify() 函式，可以將現有的列表轉換成堆積積。

import heapq

myheap = [3, 1, 4, 1, 5, 9, 2, 6, 5]
heapq.heapify(myheap)
print(myheap)  # Output: [1, 1, 2, 3, 5, 9, 4, 6, 5]

內容解密：

1. 引入 heapq 模組： 首先，我們需要引入 Python 的 heapq 模組，這個模組提供了堆積積（heap）資料結構的相關函式。
2. 建立列表： 建立一個名為 myheap 的列表，其中包含一些數值。這個列表將被轉換為堆積積。
3. heapify 轉換： 呼叫 heapq.heapify(myheap) 函式。這個函式會將 myheap 列表轉換成一個最小堆積積（min-heap）。最小堆積積的特性是父節點的值小於或等於其子節點的值。經過 heapify 處理後，myheap 列表的元素會重新排列，以符合堆積積的特性。
4. 印出結果： 最後，使用 print(myheap) 印出經過 heapify 處理後的列表。你會看到列表中的元素已經被重新排列，最小的元素被放在了列表的最前面。

從堆積積中取出最小元素

使用 heappop() 函式可以取出堆積積中的最小元素，並同時調整堆積積結構。

import heapq

# 從堆積積中取出最小元素
myheap = [3, 1, 4, 1, 5, 9, 2, 6, 5]
heapq.heapify(myheap)
print(heapq.heappop(myheap))  # Output: 1
print(heapq.heappop(myheap))  # Output: 1

內容解密：

1. 引入 heapq 模組： 引入 Python 的 heapq 模組，以便使用堆積積相關的函式。
2. 建立列表並轉換為堆積積： 建立一個名為 myheap 的列表，並使用 heapq.heapify(myheap) 將其轉換為最小堆積積。
3. 取出最小元素： 呼叫 heapq.heappop(myheap) 函式。這個函式會從 myheap 堆積積中取出最小的元素（也就是堆積積頂端的元素），並將堆積積重新調整，以保持堆積積的特性。第一次呼叫 heappop 時，會取出數值 1。
4. 再次取出最小元素： 再次呼叫 heapq.heappop(myheap) 函式，這時會取出堆積積中下一個最小的元素。由於列表中有兩個 1，所以第二次呼叫 heappop 時，也會取出數值 1。
5. 印出結果： 使用 print() 函式印出每次 heappop 取出的元素。

向堆積積中加入元素

使用 heappush() 函式可以將新元素加入堆積積中，並自動調整堆積積結構。

import heapq

# 向堆積積中加入元素
myheap = [3, 1, 4, 1, 5, 9, 2, 6, 5]
heapq.heapify(myheap)
heapq.heappush(myheap, 0)
heapq.heappush(myheap, 7)
print(myheap)  # Output: [0, 1, 2, 3, 5, 9, 4, 6, 5, 7]

內容解密：

1. 引入 heapq 模組： 引入 Python 的 heapq 模組，以便使用堆積積相關的函式。
2. 建立列表並轉換為堆積積： 建立一個名為 myheap 的列表，並使用 heapq.heapify(myheap) 將其轉換為最小堆積積。
3. 加入新元素： 呼叫 heapq.heappush(myheap, 0) 將數值 0 加入堆積積中。heappush 函式會將新元素插入堆積積，並調整堆積積的結構，以保持最小堆積積的特性。
4. 再次加入新元素： 呼叫 heapq.heappush(myheap, 7) 將數值 7 加入堆積積中。
5. 印出結果： 使用 print(myheap) 印出經過插入操作後的堆積積。你會看到新元素已經被正確地插入到堆積積中，與堆積積的結構仍然保持有效。

堆積積的大小

使用 len() 函式可以取得堆積積的大小，也就是堆積積中元素的個數。

import heapq

# 檢查堆積積的大小
myheap = [3, 1, 4, 1, 5, 9, 2, 6, 5]
heapq.heapify(myheap)
print(len(myheap))  # Output: 9

內容解密：

1. 引入 heapq 模組： 引入 Python 的 heapq 模組，以便使用堆積積相關的函式。
2. 建立列表並轉換為堆積積： 建立一個名為 myheap 的列表，並使用 heapq.heapify(myheap) 將其轉換為最小堆積積。
3. 檢查堆積積大小： 呼叫 len(myheap) 函式，這個函式會回傳 myheap 列表中元素的個數，也就是堆積積的大小。
4. 印出結果： 使用 print() 函式印出堆積積的大小。

樹 (Tree)：組織階層式資料

樹是一種階層式的資料結構，由節點和邊組成。每個樹都有一個根節點，其他節點都是根節點的子節點。樹在電腦科學中被廣泛應用，例如檔案系統、組織結構等。

建立樹

在 Python 中，可以使用類別來建立樹的節點，並使用物件來表示樹的結構。

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# 建立一個樹
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

內容解密：

1. 定義 Node 類別： 首先，定義一個名為 Node 的類別，這個類別代表樹的節點。每個節點都有三個屬性：
   • data：儲存節點的資料。
   • left：指向左子節點的指標。
   • right：指向右子節點的指標。
2. 初始化節點： 在 Node 類別的 __init__ 方法中，我們初始化節點的資料，並將 left 和 right 指標設為 None，表示這個節點一開始沒有子節點。
3. 建立樹的結構： 接著，我們建立一個樹的結構。首先，建立一個根節點 root，其資料為 1。然後，建立根節點的左子節點 root.left，其資料為 2，以及右子節點 root.right，其資料為 3。
4. 建立更深層的節點： 繼續建立左子節點的子節點 root.left.left，其資料為 4，以及 root.left.right，其資料為 5。這樣就建立了一個簡單的樹狀結構。

走訪樹

樹有多種走訪方式，常見的有以下三種：

• 中序走訪（Inorder Traversal）： 先走訪左子樹，再走訪根節點，最後走訪右子樹。
• 前序走訪（Preorder Traversal）： 先走訪根節點，再走訪左子樹，最後走訪右子樹。
• 後序走訪（Postorder Traversal）： 先走訪左子樹，再走訪右子樹，最後走訪根節點。

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# 建立一個樹
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

def inorder(node):
    if node is not None:
        inorder(node.left)
        print(node.data)
        inorder(node.right)

# 中序走訪樹
inorder(root)

def preorder(node):
    if node is not None:
        print(node.data)
        preorder(node.left)
        preorder(node.right)

# 前序走訪樹
preorder(root)

def postorder(node):
    if node is not None:
        postorder(node.left)
        postorder(node.right)
        print(node.data)

# 後序走訪樹
postorder(root)

內容解密：

1. Inorder (中序走訪):
   • 遞迴呼叫： 首先，遞迴地呼叫 inorder(node.left)，也就是先走訪目前節點的左子樹。
   • 印出節點資料： 當左子樹走訪完畢後，印出目前節點的資料 print(node.data)。
   • 遞迴呼叫： 最後，遞迴地呼叫 inorder(node.right)，也就是走訪目前節點的右子樹。
   • 走訪順序： 左 -> 根 -> 右
2. Preorder (前序走訪):
   • 印出節點資料： 首先，印出目前節點的資料 print(node.data)。
   • 遞迴呼叫： 接著，遞迴地呼叫 preorder(node.left)，也就是走訪目前節點的左子樹。
   • 遞迴呼叫： 最後，遞迴地呼叫 preorder(node.right)，也就是走訪目前節點的右子樹。
   • 走訪順序： 根 -> 左 -> 右
3. Postorder (後序走訪):
   • 遞迴呼叫： 首先，遞迴地呼叫 postorder(node.left)，也就是先走訪目前節點的左子樹。
   • 遞迴呼叫： 接著，遞迴地呼叫 postorder(node.right)，也就是走訪目前節點的右子樹。
   • 印出節點資料： 最後，印出目前節點的資料 print(node.data)。
   • 走訪順序： 左 -> 右 -> 根

在樹中尋找元素

可以使用遞迴函式在樹中尋找特定的元素。

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# 建立一個樹
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

def find(node, data):
    if node is None:
        return False
    elif node.data == data:
        return True
    elif data < node.data:
        return find(node.left, data)
    else:
        return find(node.right, data)

# 在樹中尋找元素
print(find(root, 2))  # Output: True
print(find(root, 6))  # Output: False

內容解密：

1. 基本情況：
   • 節點為空： 首先檢查目前節點 node 是否為 None。如果節點為空，表示已經走訪到樹的末端，與沒有找到目標資料，因此回傳 False。
   • 找到目標資料： 接著檢查目前節點的資料 node.data 是否等於目標資料 data。如果相等，表示找到了目標資料，因此回傳 True。
2. 遞迴搜尋：
   • 目標資料較小： 如果目標資料 data 小於目前節點的資料 node.data，表示目標資料可能位於左子樹中。因此，遞迴呼叫 find(node.left, data)，在左子樹中繼續搜尋。
   • 目標資料較大： 如果目標資料 data 大於目前節點的資料 node.data，表示目標資料可能位於右子樹中。因此，遞迴呼叫 find(node.right, data)，在右子樹中繼續搜尋。

圖 (Graph)：表示物件間的關係

圖是一種用來表示物件之間關係的資料結構，由節點（或稱為頂點）和邊組成。圖在社交網路、地圖導航等領域有廣泛的應用。

建立圖

在 Python 中，可以使用類別來建立圖的節點，並使用列表來表示節點之間的連線關係。

class Node:
    def __init__(self, data):
        self.data = data
        self.neighbors = []

# 建立一個圖
A = Node('A')
B = Node('B')
C = Node('C')
D = Node('D')
E = Node('E')
F = Node('F')
G = Node('G')
H = Node('H')
A.neighbors = [B, C, D]
B.neighbors = [A, E]
C.neighbors = [A, F]
D.neighbors = [A, G, H]
E.neighbors = [B]
F.neighbors = [C]
G.neighbors = [D, H]
H.neighbors = [D, G]

內容解密：

1. 定義 Node 類別： 首先，定義一個名為 Node 的類別，這個類別代表圖的節點。每個節點都有兩個屬性：
   • data：儲存節點的資料。
   • neighbors：一個列表，儲存與目前節點相鄰的節點。
2. 初始化節點： 在 Node 類別的 __init__ 方法中，我們初始化節點的資料，並將 neighbors 列表設為空列表，表示這個節點一開始沒有相鄰的節點。
3. 建立圖的節點： 接著，我們建立圖的各個節點，例如 A、B、C 等等，每個節點都使用 Node 類別建立。
4. 建立節點之間的連線關係： 建立節點之間的連線關係。例如，A.neighbors = [B, C, D] 表示節點 A 與節點 B、C、D 相鄰。

走訪圖

圖有多種走訪方式，常見的有以下兩種：

• 深度優先搜尋（Depth-First Search, DFS）： 從起始節點開始，沿著圖的深度方向走訪，直到無法繼續深入為止，然後回溯到上一個節點，繼續走訪其他分支。
• 廣度優先搜尋（Breadth-First Search, BFS）： 從起始節點開始，先走訪所有與起始節點相鄰的節點，然後再走訪與這些相鄰節點相鄰的節點，以此類別推。

class Node:
    def __init__(self, data):
        self.data = data
        self.neighbors = []

# 建立一個圖
A = Node('A')
B = Node('B')
C = Node('C')
D = Node('D')
E = Node('E')
F = Node('F')
G = Node('G')
H = Node('H')
A.neighbors = [B, C, D]
B.neighbors = [A, E]
C.neighbors = [A, F]
D.neighbors = [A, G, H]
E.neighbors = [B]
F.neighbors = [C]
G.neighbors = [D, H]
H.neighbors = [D, G]

def dfs(node, visited):
    visited.add(node)
    print(node.data)
    for neighbor in node.neighbors:
        if neighbor not in visited:
            dfs(neighbor, visited)

# 深度優先搜尋圖
visited = set()
dfs(A, visited)

def bfs(node):
    visited = set()
    queue = [node]
    visited.add(node)
    while queue:
        curr_node = queue.pop(0)
        print(curr_node.data)
        for neighbor in curr_node.neighbors:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# 廣度優先搜尋圖
bfs(A)

內容解密：

1. DFS (深度優先搜尋):
   • 標記為已走訪： 首先，將目前節點 node 加入 visited 集合中，表示這個節點已經被走訪過了。
   • 印出節點資料： 接著，印出目前節點的資料 print(node.data)。
   • 走訪相鄰節點： 走訪目前節點的所有相鄰節點 neighbor。
   • 遞迴呼叫： 如果相鄰節點尚未被走訪過（也就是 neighbor not in visited），則遞迴呼叫 dfs(neighbor, visited)，繼續以深度優先的方式走訪相鄰節點。
2. BFS (廣度優先搜尋):
   • 初始化：
     • 建立一個 visited 集合，用來記錄已經走訪過的節點。
     • 建立一個佇列 queue，並將起始節點 node 加入佇列中。
     • 將起始節點標記為已走訪。
   • 迴圈：
     • 當佇列不為空時，重複執行以下步驟：
     • 從佇列中取出第一個節點 curr_node。
     • 印出節點資料。
     • 走訪目前節點的所有相鄰節點 neighbor。
     • 如果相鄰節點尚未被走訪過，則將其加入佇列，並標記為已走訪。

在圖中尋找路徑

可以使用遞迴函式在圖中尋找兩個節點之間的路徑。

class Node:
    def __init__(self, data):
        self.data = data
        self.neighbors = []

# 建立一個圖
A = Node('A')
B = Node('B')
C = Node('C')
D = Node('D')
E = Node('E')
F = Node('F')
G = Node('G')
H = Node('H')
A.neighbors = [B, C, D]
B.neighbors = [A, E]
C.neighbors = [A, F]
D.neighbors = [A, G, H]
E.neighbors = [B]
F.neighbors = [C]
G.neighbors = [D, H]
H.neighbors = [D, G]

def find_path(start_node, end_node, visited, path):
    visited.add(start_node)
    path.append(start_node)
    if start_node == end_node:
        return path
    for neighbor in start_node.neighbors:
        if neighbor not in visited:
            result = find_path(neighbor, end_node, visited, path)
            if result:
                return result
    path.pop()

# 在圖中尋找路徑
visited = set()
path = []
result = find_path(A, H, visited, path)
print([node.data for node in result])

內容解密：

1. 標記與記錄：
   • 將目前節點 start_node 標記為已走訪，加入 visited 集合中。
   • 將目前節點加入路徑 path 列表中。
2. 找到目標：
   • 如果目前節點等於目標節點 end_node，表示已經找到路徑，直接回傳 path。
3. 遞迴搜尋：
   • 走訪目前節點的所有相鄰節點 neighbor。
   • 如果相鄰節點尚未被走訪過，則遞迴呼叫 find_path(neighbor, end_node, visited, path)，繼續搜尋路徑。
   • 如果遞迴呼叫找到路徑（也就是 result 不為空），則直接回傳 result。
4. 回溯：
   • 如果所有相鄰節點都走訪過，但仍然沒有找到路徑，表示目前路徑是錯誤的，需要回溯。
   • 將目前節點從路徑 path 列表中移除。

玄貓今天介紹了 Python 中三種重要的資料結構：堆積積、樹和圖。希望透過這些實戰範例，能幫助你更深入地理解它們的特性和應用場景。掌握這些資料結構，將使你在程式設計的道路上更上一層樓。

程式碼尋徑：Python 圖形結構的優雅解法

在圖形結構中尋找特定節點間的路徑，是許多演算法的核心問題。以下程式碼延續前文，展示如何使用 Python 實作尋徑功能：

class Node:
    def __init__(self, data):
        self.data = data
        self.neighbors = []

    def add_neighbor(self, node):
        self.neighbors.append(node)

def find_path(start_node, end_node, visited, path):
    visited.add(start_node)
    path.append(start_node)

    if start_node == end_node:
        return path

    for neighbor in start_node.neighbors:
        if neighbor not in visited:
            result = find_path(neighbor, end_node, visited, path)
            if result:
                return result

    path.pop()
    return None

# 建立圖形結構
A = Node('A')
B = Node('B')
C = Node('C')
D = Node('D')
E = Node('E')
F = Node('F')
G = Node('G')
H = Node('H')

A.add_neighbor(B)
A.add_neighbor(C)
B.add_neighbor(D)
C.add_neighbor(E)
D.add_neighbor(F)
E.add_neighbor(G)
F.add_neighbor(H)

# 尋找從 A 到 H 的路徑
visited = set()
path = []
result = find_path(A, H, visited, path)
if result:
    print('Path found:', [node.data for node in result])
else:
    print('Path not found')

內容解密

1. Node 類別：定義圖形中的節點，包含資料和相鄰節點列表。
2. find_path 函式：使用遞迴方式尋找路徑，visited 集合追蹤已存取節點，path 列表記錄當前路徑。
3. 圖形建立：手動建立一個圖形，節點間的連線使用 add_neighbor 方法。
4. 路徑尋找：呼叫 find_path 函式，如果找到路徑則印出，否則顯示未找到。

玄貓觀點：圖形結構的應用與演算法選擇

圖形結構在現實世界中有廣泛應用，例如社交網路、地圖導航和網路路由等。選擇合適的圖形遍歷演算法（如 DFS 或 BFS）取決於具體應用場景和需求。