Prim のアルゴリズムを Python で記述するにはどうすればよいですか?

Prim のアルゴリズムを Python で記述するにはどうすればよいですか?

Prim のアルゴリズムは、最小スパニング ツリー問題を解決するための古典的なアルゴリズムで、無向接続グラフの最小スパニング ツリーを見つけることができます。この記事では、Python を使用して Prim のアルゴリズムを記述する方法を、具体的なコード例とともに紹介します。

まず第一に、Prim のアルゴリズムの基本原理を理解する必要があります。アルゴリズムは開始ノードから開始し、グラフ内のすべてのノードがカバーされるまでツリーの境界を徐々に拡張します。具体的には、Prim のアルゴリズムは毎回ツリーに最も近いノードを選択してスパニング ツリーに追加し、このノードをスパニング ツリー内のノードに接続するエッジを候補エッジ セットに追加します。次に、候補エッジのセットから最小の重みを持つエッジが選択され、スパニング ツリーにすべてのノードが含まれるまでこのプロセスが繰り返されます。

以下は、Python を使用して Prim のアルゴリズムを実装するコード例です。

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 メソッドを使用して、候補エッジ セット内の最小の重みを持つエッジに対応するノードを選択し、キー配列と親配列を更新します。

テスト例では、5 つのノードを含むグラフを作成し、その隣接行列表現を与えました。コードの出力は、最小スパニング ツリーのエッジとその重みです。

つまり、Python のシンプルさと読みやすさにより、Prim のアルゴリズムを比較的簡単に実装できます。 Prim のアルゴリズムの基本原理を理解し、上記のコード例を使用すると、Prim のアルゴリズムの実装を簡単に作成して実行できます。この記事が Prim のアルゴリズムを学ぶのに役立つことを願っています。

以上がPrim のアルゴリズムを Python で記述するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。