Python を使用してクラスカルのアルゴリズムを実装するにはどうすればよいですか?

Python を使用して Kruskal のアルゴリズムを実装するにはどうすればよいですか?

はじめに:
Kruskal のアルゴリズムは、最小スパニング ツリーを解くための古典的なアルゴリズムであり、指定された重み付き接続グラフ内で合計重みが最小のスパニング ツリーを見つけることができます。この記事では、Python を使用して Kruskal のアルゴリズムを実装する方法を紹介し、詳細なコード例を示します。

1. アルゴリズムの紹介:
   クラスカルのアルゴリズムの基本的な考え方は、接続されたグラフ内のすべてのエッジを重みに従って並べ替え、小さいエッジから大きいエッジまで選択することです。現在選択されているエッジはループではありません。ループが形成されると、そのループは最小スパニング ツリーに追加され、訪問済みとしてマークされます。最小スパニング ツリーのエッジの数が、グラフの頂点の数から 1 を引いた数に等しくなるまで。
2. 実装手順:
   (1) グラフのクラスを定義し、グラフの頂点と辺の数を初期化します。
   (2) 各エッジのクラスを定義し、エッジの始点、終点、重みを初期化します。
   (3) ルート ノードの検索やセットの結合など、セットを実装および初期化する関数を作成します。
   (4) クラスカルのアルゴリズムを実装する main 関数を作成します。これには、エッジの並べ替え、エッジを 1 つずつ選択してサイクルを形成するかどうかを決定すること、最小スパニング ツリーにエッジを追加すること、最小スパニング ツリーの合計重みを計算することが含まれます。 。
3. コード例:

class Graph:
    def __init__(self, vertices):
        self.V = vertices  # 顶点数
        self.graph = []

    # 添加边
    def add_edge(self, u, v, weight):
        self.graph.append([u, v, weight])

    # 查找根节点
    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    # 合并集合
    def union(self, parent, rank, x, y):
        root_x = self.find(parent, x)
        root_y = self.find(parent, y)
        if rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        elif rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        else:
            parent[root_y] = root_x
            rank[root_x] += 1

    # 克鲁斯卡尔算法
    def kruskal_algorithm(self):
        result = []
        i = 0
        e = 0
        self.graph = sorted(self.graph, key=lambda item: item[2])  # 按照权值排序
        parent = []
        rank = []

        for node in range(self.V):
            parent.append(node)
            rank.append(0)

        while e < self.V - 1:
            u, v, weight = self.graph[i]
            i += 1
            x = self.find(parent, u)
            y = self.find(parent, v)

            if x != y:
                e += 1
                result.append([u, v, weight])
                self.union(parent, rank, x, y)

        # 打印最小生成树
        print("最小生成树：")
        for u, v, weight in result:
            print(f"{u} -- {v}     {weight}")

        # 计算最小生成树的总权值
        total_weight = sum(weight for u, v, weight in result)
        print("最小生成树的总权值：", total_weight)


if __name__ == '__main__':
    g = Graph(6)
    g.add_edge(0, 1, 4)
    g.add_edge(0, 2, 3)
    g.add_edge(1, 2, 1)
    g.add_edge(1, 3, 2)
    g.add_edge(2, 3, 4)
    g.add_edge(2, 4, 3)
    g.add_edge(3, 4, 2)
    g.add_edge(3, 5, 1)
    g.add_edge(4, 5, 6)

    g.kruskal_algorithm()

4. 結果分析:
   上記のコードは典型的な例であり、6 つの頂点を含む重み付き無向グラフを構築し、Kruskal のアルゴリズムを使用します。最小スパニングツリーを解決します。プログラムは、最小スパニング ツリーのエッジと最小スパニング ツリーの合計の重みを出力します。

結論:
Kruskal のアルゴリズムは、接続されたグラフの最小スパニング ツリーを解くための効率的な方法です。エッジをソートし、セットをマージすることで、最小値をもつ最小スパニング ツリーを取得できます。重みの合計スパニング ツリー。 Python を使用してクラスカルのアルゴリズムを実装すると、アルゴリズムの原理とプロセスをより深く理解し、実際の問題に簡単に適用できます。

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