Python底層技術揭秘：如何實作圖演算法

隨著電腦科技的不斷發展，圖論（graph theory）及其相關演算法已經成為了電腦領域中非常重要的一部分。而對於Python程式設計師來說，掌握這些底層技術不僅可以提高程式碼的效率和質量，還有助於優化程式的效能和開發效率。

本文將介紹Python實作圖演算法的底層技術，包括圖的儲存方式、遍歷方式、最短路徑演算法、最小生成樹演算法以及拓樸排序演算法，重點介紹各演算法的實作思路和程式碼範例。

一、圖的儲存方式

在Python中，我們可以使用鄰接矩陣或鄰接表來儲存圖。

1、鄰接矩陣

鄰接矩陣是一個二維矩陣，其中頂點的行和列分別對應兩個頂點。若兩個頂點之間有邊相連，則該位置值設為1或其邊權值；否則設為0。例如，下面是鄰接矩陣的例子：

graph = [[0, 1, 1, 0], 
         [1, 0, 1, 1], 
         [1, 1, 0, 1], 
         [0, 1, 1, 0]]

這個矩陣表示一個無向圖，共有4個頂點，其中1、2、3之間互相有連邊。

2、鄰接表

鄰接表是字典，其中每個鍵對應一個頂點，對應的值是該頂點的鄰居頂點列表。例如：

graph = {0: [1, 2], 
         1: [0, 2, 3], 
         2: [0, 1, 3], 
         3: [1, 2]}

這個字典表示同樣的無向圖，其中每個鍵值對應一個頂點，這個頂點對應的值是這個頂點和其它頂點之間的連邊。

二、圖的遍歷方式

1、深度優先遍歷（DFS）

深度優先遍歷是搜尋所有子樹的深度方向，也就是先造訪目前頂點，然後遞歸訪問它的每一個鄰居頂點。對於每個頂點，我們必須記住它是否被訪問過；如果未訪問，就遞歸遍歷它的鄰居頂點。程式碼實作：

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next_vertex in graph[start] - visited:
        dfs(graph, next_vertex, visited)
    return visited

2、廣度優先遍歷（BFS）

廣度優先遍歷是搜尋所有子樹的廣度方向，也就是先存取目前頂點，然後存取它的所有鄰居頂點。對於每個頂點，我們必須記住它是否被訪問過；如果未訪問，請加入佇列中並標記為已訪問，然後遞歸它的鄰居頂點。程式碼實作：

from collections import deque

def bfs(graph, start):
    visited, queue = set(), deque([start])
    visited.add(start)
    while queue:
        vertex = queue.popleft()
        print(vertex)
        for next_vertex in graph[vertex] - visited:
            visited.add(next_vertex)
            queue.append(next_vertex)

三、圖演算法

1、最短路徑演算法

#最短路徑演算法是尋找圖中兩個頂點之間最短路徑的演算法。其中，Dijkstra演算法用於有向無環圖（DAG），Bellman-Ford演算法適用於任何圖。

（1）Dijkstra演算法

Dijkstra演算法用於有向無環圖，並且只能處理非負權值的圖。這個演算法的核心是貪心策略，即假定路徑是由許多獨立的單元（節點）組成的，對每個單元的最短路徑進行逐一考慮，找到全局最短路。程式碼實作：

import heapq
import sys

def dijkstra(graph, start):
    visited = set()
    distance = {vertex: sys.maxsize for vertex in graph}
    distance[start] = 0
    queue = [(0, start)]
    while queue:
        dist, vertex = heapq.heappop(queue)
        if vertex not in visited:
            visited.add(vertex)
            for neighbor, weight in graph[vertex].items():
                total_distance = dist + weight
                if total_distance < distance[neighbor]:
                    distance[neighbor] = total_distance
                    heapq.heappush(queue, (total_distance, neighbor))
    return distance

（2）Bellman-Ford演算法

Bellman-Ford演算法能夠處理任何圖，包括負權值的圖。此演算法透過動態規劃的方式來解決最短路徑問題。程式碼實作：

import sys

def bellman_ford(graph, start):
    distance = {vertex: sys.maxsize for vertex in graph}
    distance[start] = 0
    for _ in range(len(graph) - 1):
        for vertex in graph:
            for neighbor, weight in graph[vertex].items():
                total_distance = distance[vertex] + weight
                if total_distance < distance[neighbor]:
                    distance[neighbor] = total_distance
    return distance

2、最小生成樹演算法

最小生成樹問題是尋找無向加權圖的所有頂點所構成的子圖，使得該子圖中所有邊的權值總和最小。其中，Kruskal和Prim演算法都是解決此問題的經典演算法。

（1）Kruskal演算法

Kruskal演算法是一種貪心演算法，從所有邊中選取權值最小的邊，依序尋找下一條權值最小的邊，直到頂點數與邊數匹配為止。程式碼實作：

def kruskal(graph):
    parent = {}
    rank = {}
    for vertex in graph:
        parent[vertex] = vertex
        rank[vertex] = 0
    minimum_spanning_tree = set()
    edges = list(graph.edges)
    edges.sort()
    for edge in edges:
        weight, vertex1, vertex2 = edge
        root1 = find(parent, vertex1)
        root2 = find(parent, vertex2)
        if root1 != root2:
            minimum_spanning_tree.add(edge)
            if rank[root1] > rank[root2]:
                parent[root2] = root1
            else:
                parent[root1] = root2
                if rank[root1] == rank[root2]:
                    rank[root2] += 1
    return minimum_spanning_tree

（2）Prim演算法

Prim演算法開始任選一個頂點作為起點，每次根據當前生成樹與圖中其它頂點的距離，以及其它頂點與當前生成樹的最小距離來選擇一個新的頂點加入生成樹。程式碼實作：

import heapq

def prim(graph, start):
    minimum_spanning_tree = set()
    visited = set(start)
    edges = list(graph[start].items())
    heapq.heapify(edges)
    while edges:
        weight, vertex1 = heapq.heappop(edges)
        if vertex1 not in visited:
            visited.add(vertex1)
            minimum_spanning_tree.add((weight, start, vertex1))
            for vertex2, weight in graph[vertex1].items():
                if vertex2 not in visited:
                    heapq.heappush(edges, (weight, vertex1, vertex2))
    return minimum_spanning_tree

3、拓樸排序演算法

拓樸排序演算法主要用於處理有向無環圖中的邏輯依賴關係，通常用來解決編譯依賴或任務排程問題。程式碼實作：

from collections import defaultdict

def topological_sort(graph):
    in_degree = defaultdict(int)
    for vertex1 in graph:
        for vertex2 in graph[vertex1]:
            in_degree[vertex2] += 1
    queue = [vertex for vertex in graph if in_degree[vertex] == 0]
    result = []
    while queue:
        vertex = queue.pop()
        result.append(vertex)
        for next_vertex in graph[vertex]:
            in_degree[next_vertex] -= 1
            if in_degree[next_vertex] == 0:
                queue.append(next_vertex)
    if len(result) != len(graph):
        raise ValueError("The graph contains a cycle")
    return result

四、總結

本文介紹了Python實作圖演算法的底層技術，包括圖的儲存方式、遍歷方式、最短路徑演算法、最小生成樹演算法以及拓樸排序演算法，透過具體的程式碼範例，讓讀者了解每種演算法的實作想法和程式碼實作細節。在實際開發過程中，讀者可以根據自己的需求選擇不同的演算法，以提高程式的效率和品質。

以上是Python底層技術揭秘：如何實作圖演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！