Python WebAcademy

学習モード

グラフ理論とグラフアルゴリズム

Section 9 / 12

KruskalアルゴリズムとUnion-Findの基礎

Kruskalアルゴリズムは、グラフの最小全域木（MST）を見つけるための効率的な手法です。このアルゴリズムは、辺を重みの昇順にソートし、最小の重みを持つ辺から順に選択していき、サイクルを形成しないように注意しながら進めます。Union-Find（またはディスジョイントセット）は、サイクルを検出し、異なる集合を効率的に管理するために使用されます。

Kruskalアルゴリズムの流れ

  1. グラフのすべての辺を重みの昇順にソートします。
  2. ソートされた辺を順に見ていきます。
  3. それぞれの辺が追加されたときにサイクルを形成しないか確認します。
  4. サイクルを形成しない場合、その辺を最小全域木に追加します。
  5. すべての辺を処理するまで続けます。

Union-Findの基本

Union-Findは、集合の管理を効率的に行うためのデータ構造です。以下の二つの主要な操作を提供します。

  • Find: 特定の要素が属している集合を見つけます。
  • Union: 二つの集合を一つに結合します。

Union-Findは、パス圧縮とランク（サイズ）による統合を行うことで、これらの操作を非常に効率的に実行します。

サンプルコード

以下に、Kruskalアルゴリズムの実装を示します。この実装にはUnion-Findも含まれています。

class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [1] * size

    def find(self, p):
        if self.parent[p] != p:
            self.parent[p] = self.find(self.parent[p])  # Path compression
        return self.parent[p]

    def union(self, p, q):
        rootP = self.find(p)
        rootQ = self.find(q)

        if rootP != rootQ:
            # Union by rank
            if self.rank[rootP] > self.rank[rootQ]:
                self.parent[rootQ] = rootP
            elif self.rank[rootP] < self.rank[rootQ]:
                self.parent[rootP] = rootQ
            else:
                self.parent[rootQ] = rootP
                self.rank[rootP] += 1

class Edge:
    def __init__(self, u, v, weight):
        self.u = u
        self.v = v
        self.weight = weight

def kruskal(vertices, edges):
    edges.sort(key=lambda edge: edge.weight)  # Sort edges by weight
    uf = UnionFind(vertices)
    mst = []

    for edge in edges:
        if uf.find(edge.u) != uf.find(edge.v):
            uf.union(edge.u, edge.v)
            mst.append(edge)

    return mst

# Example usage
vertices = 4
edges = [
    Edge(0, 1, 10),
    Edge(0, 2, 6),
    Edge(0, 3, 5),
    Edge(1, 3, 15),
    Edge(2, 3, 4)
]

mst = kruskal(vertices, edges)
for edge in mst:
    print(f"Edge: {edge.u} - {edge.v} with weight: {edge.weight}")

コードの解説

  1. UnionFindクラス:
  2. __init__: 親ノードとランクを初期化します。
  3. find: 指定した要素の親を再帰的に見つけ、パス圧縮を行います。

  4. union: 二つの要素を結合し、ランクに基づいて木の高さを最小限に保ちます。

  5. Edgeクラス:

  6. 辺の情報（端点と重み）を持っています。

  7. kruskal関数:

  8. 引数として頂点数と辺のリストを受け取ります。

  9. 辺を重みでソートし、Union-Findを使用して最小全域木を構成します。

  10. 例の使用法:

  11. グラフの頂点と辺を定義し、Kruskalアルゴリズムを呼び出して最小全域木を出力します。

このコードを実行すると、最小全域木に含まれる辺が表示されます。これにより、KruskalアルゴリズムとUnion-Findの基本的な理解が深まるでしょう。

前に戻る