More than 3 years have passed since last update.

[競プロ用]最小全域木まとめ

Last updated at 2020-06-01Posted at 2020-05-30

最小全域木を求める手法

プリム法
クラスカル法

使い分け

議論になっていた
https://togetter.com/li/776049

入力形式で使い分ける？

ノード間のコストが行列で渡される → プリム法
2点のノードとそのコストの組み合わせで渡される。 → クラスカル法

プリム法

任意のスタート地点から始める。
移動可能なノードのうち最も低コストで移動できるものを選び繋ぐ。
2を繰り返し、全てのノードを繋いだ時点で最小全域木となる。

どうすればいいか

ノードを繋ぐ度に選択肢が広がっていき、常にその中で最小のものを選択したい。
→ 優先度付きキュー(heapq)を用いる。

heapqにタプルを渡すと一番目の要素で最小値を判断されることを利用する。

何がいいのか

O(ElogV)。
フィボナッチヒープを使うとより早い？

イメージ

使用例

AOJ ALDS1_12_A

プリム法

import heapq

def main():
    n = int(input())
    next = []   # 隣接管理のリスト
    for _ in range(n):
        l = list(map(int, input().split()))
        next.append([(c, i) for i, c in enumerate(l) if c != -1])
    visited = [0] * n
    connection = 0
    q = [(0, 0)]    # (cost, v)
    heapq.heapify(q)
    ans = 0
    while len(q):
        cost, v = heapq.heappop(q)
        if visited[v]:
            continue

        # そのノードと繋げる
        visited[v] = 1
        connection += 1
        ans += cost
        
        # 新たに繋げたノードから行けるところをエンキュー
        for i in next[v]:
            heapq.heappush(q, i)
        
        # 全部のノードが繋がったら終了
        if connection == n:
            break
    print(ans)
    return

クラスカル法

全ての辺を重みの小さいものから順に選びとっていく。
その過程で閉路を作ってしまうものは捨てる。全ての辺に対してこれを行う。
最終的に選び取った辺のみで最小全域木となる。

どうすればいいか

1 → 辺のコストを元にソートする。リストの各要素をタプルにしてソートすると1番目の要素でソートされるテクニックを利用。
2 → 「閉路ができる」＝「既に2点が繋がっているところに辺を作る」なのでUnionFind木で確認する。

何がいいのか

O(ElogV)。

イメージ

使用例

AOJ GRL_2_A

クラスカル法

def main():
    V, E = map(int, input().split())
    uf = UnionFind(V)

    # 1の過程
    edges = []
    for _ in range(E):
        s, t, w = map(int, input().split())
        edges.append((w, s, t))
    edges.sort()

    # 2の過程
    cost = 0
    for edge in edges:
        w, s, t = edge
        if not uf.same(s, t):
            cost += w
            uf.union(s, t)
    print(cost)
    return

追記(6/1)

考えること

辺の数が膨大になるとO(ElogV)のオーダーでは間に合わないので、非常に辺が多い場合には候補となる辺を減らさないかを考えるのが有力。 → 応用例参照
最小全域木のこれらの手法は多重辺があっても使用できる。→ 同じコストの辺を重複してカウントしても問題ない

応用例

ARC076 D - Built?
1つめ：Eが膨大なケースでは予め減らすことを検討する。
→今回はx座標上でもy座標上でも隣接しない町同士は選ばれないことを利用。
2つめ：x軸、y軸ともに隣接する町に該当する場合には2回カウントされるが気にしない。

def main():
    N = int(input())
    nodes = []
    for i in range(N):
        x, y = map(int, input().split())
        nodes.append((x, y, i))  # 座標に一意性があればタプルのままUnionFindにぶっこめるが、同一座標に町があるケースがあるのでナンバリングする。

    uf = UnionFind(N)
    nodes_sorted_by_x = sorted(nodes)
    nodes_sorted_by_y = sorted(nodes, key=lambda i: i[1])

    edges = []
    for i in range(N - 1):
        dx = abs(nodes_sorted_by_x[i][0] - nodes_sorted_by_x[i + 1][0])
        dy = abs(nodes_sorted_by_x[i][1] - nodes_sorted_by_x[i + 1][1])
        cost = min(dx, dy)
        edges.append((cost, nodes_sorted_by_x[i][2],  nodes_sorted_by_x[i + 1][2]))

    for i in range(N - 1):
        dx = abs(nodes_sorted_by_y[i][0] - nodes_sorted_by_y[i + 1][0])
        dy = abs(nodes_sorted_by_y[i][1] - nodes_sorted_by_y[i + 1][1])
        cost = min(dx, dy)
        edges.append((cost, nodes_sorted_by_y[i][2],  nodes_sorted_by_y[i + 1][2]))

    edges.sort()
        
    ans = 0
    for edge in edges:
        w, s, t = edge
        if not uf.same(s, t):
            ans += w
            uf.union(s, t)
    print(ans)

Appendix

タプルのリストをソートする際のキーを指定する。

# 通常はタプルの1番目の要素でソートされる。
sortedByFirstKey  = sorted(listOfTuple)
# Keyにラムダ式を指定し、タプルの2つ目の要素でソートするようにする。
sortedBySecondKey = sorted(listOfTuple, key=lambda i: i[1])
# reverse
sortedBySecondKey = sorted(listOfTuple, key=lambda i: i[1], reverse=True)

特に辞書のリストをソートしようとするとエラーするので上記のようにkeyを指定してあげる必要がある。
reverseで逆順を指定する。sort()でもsorted()でも使用可能。

参考

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up