如何用Python寫普里姆演算法？

如何用Python寫普里姆演算法？

普里姆演算法（Prim's algorithm）是解決最小生成樹問題的一種經典演算法，它能夠找到一個無向連通圖的最小生成樹。本文將介紹如何使用Python編寫普里姆演算法，並附上具體的程式碼範例。

首先，我們需要了解普里姆演算法的基本原理。演算法從一個起始節點開始，逐步擴展樹的邊界，直到覆蓋了圖中的所有節點。具體而言，普里姆演算法每次選擇一個離樹最近的節點，並將其加入生成樹中，然後將該節點與生成樹中的節點相連的邊新增至候選邊集中。然後，從候選邊集中選擇權重最小的邊，並重複這個過程，直到生成樹包含了所有節點。

以下是使用Python實作普里姆演算法的程式碼範例：

import sys

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]

    def printMST(self, parent):
        print("Edge     Weight")
        for i in range(1, self.V):
            print(parent[i], "-", i, "    ", self.graph[i][parent[i]])

    def minKey(self, key, mstSet):
        min = sys.maxsize
        min_index = None

        for v in range(self.V):
            if key[v] < min and not mstSet[v]:
                min = key[v]
                min_index = v

        return min_index

    def primMST(self):
        key = [sys.maxsize] * self.V
        parent = [None] * self.V
        key[0] = 0
        mstSet = [False] * self.V

        parent[0] = -1

        for _ in range(self.V):
            u = self.minKey(key, mstSet)
            mstSet[u] = True

            for v in range(self.V):
                if self.graph[u][v] > 0 and not mstSet[v] and key[v] > self.graph[u][v]:
                    key[v] = self.graph[u][v]
                    parent[v] = u

        self.printMST(parent)

# 测试示例
g = Graph(5)
g.graph = [[0, 2, 0, 6, 0],
           [2, 0, 3, 8, 5],
           [0, 3, 0, 0, 7],
           [6, 8, 0, 0, 9],
           [0, 5, 7, 9, 0]]

g.primMST()

上述程式碼中，首先定義了一個Graph類，其中包含了圖的基本操作。在primMST方法中，使用了minKey方法來選擇候選邊集中權重最小的邊對應的節點，然後更新key和parent陣列。

在測試範例中，我們建立了一個包含5個節點的圖，並給出了其鄰接矩陣表示。程式碼輸出的結果是最小生成樹的各邊及其權重。

總之，Python的簡潔和易讀性使得實現普里姆演算法變得相對容易。透過理解普里姆演算法的基本原理，並使用上述程式碼範例，可以輕鬆編寫並運行一個普里姆演算法實作。希望本文對你學習普里姆演算法有所幫助！

以上是如何用Python寫普里姆演算法？的詳細內容。更多資訊請關注PHP中文網其他相關文章！