🌳

グラフアルゴリズムの基礎を学ぶー最小全域木

2023/05/06に公開

algorithm

graph

mst

tech

この記事は、グラフアルゴリズムシリーズの4番目の記事です。

概念と表現方法
BFSとDFS
UnionFind
最小全域木→現在地
単一始点最短経路問題
全点対最短経路問題（WIP）

最小全域木（MST: Minimum Spanning Tree）とは、無向図のすべての頂点をつなぐ、ウェイトが最小となる木のことです。

出典：https://en.wikipedia.org/wiki/Minimum_spanning_tree#/media/File:Minimum_spanning_tree.svg

合計ウェイトが最小になる＝コストが最小ということなので、通信のネットワークや、道路ネットワーク、配線の設計などの最適化に運用されることが考えられます。

今までの問題は全部ウェイトなしのグラフでしたが、ウェイトありのグラフ問題を解決するときに知らないといけないのは、まずMSTがあります。MST関連のアルゴリズムは代表的に、クラスカル法（Kruskal's Algorithm）とプリム法（Prim's Algorithm）が挙げられます。

クラスカル法

この方法を一言で言えば、エッジをウェイトの昇順にソートし、その順にサイクルができない前提で、エッジを追加していくことです。下記のプリム法との共通認識として、全てのノードを訪問する必要がありますので、最終的にエッジ数が必ずn-1となります。

出典：https://commons.wikimedia.org/wiki/File:MST_kruskal_en.gif

このアルゴリズムを実装する際に幾つかのポイントがあります。

エッジをウェイトで並び替えが必要なので、どうしてもO(ElogE)のソート複雑度が発生します
エッジ追加する際に、エッジの2つのノードが直接または間接的に繋いでいるかを確認するために、UnionFindが有力

このアルゴリズムのステップは以下となります。

エッジをウェイトの降順で並び替える
UnionFind/Disjoint Set Unionを作る
全てのエッジに対して下記のループを続ける
- 2つの頂点が同じルートノードを持っているかどうかを確認する
- 同じルートノードを持っていない場合（繋いでいない）は、union操作を行い、合計ウェイトにウェイトを加える
ループが終われば合計ウェイトが最小コストとなる

// UnionFind実装は前節に参照
function kruskal(edges, numVertices) {
  edges.sort((a, b) => a[2] - b[2]);

  const uf = new UnionFind(numVertices);
  let totalCost = 0;

  for (const [src, dst, cost] of edges) {
    if (uf.find(src) !== uf.find(dst)) {
      uf.union(src, dst);
      totalCost += cost;
    }
  }

  return totalCost;
}

時間複雑度について、UnionFindは定数に見なすことができますが、上記のように並び替えのコストがあるため、O(ElogE)となります。空間複雑度について、UnionFindのrootやrankとかで保存しているので、ノード数のO(n)となります。

プリム法

この方法を一言で言えば、ある頂点から始めて、サイクルができない前提で、最小コストのエッジを選んで木を拡張していくことです。プリム方のように、探索の途中で常に最大または最小の道を選んでいくのは、貪欲法（greedy algorithm）として知られています。

出典：https://upload.wikimedia.org/wikipedia/en/9/96/Prim-animation.gif

このアルゴリズムを実装する際に幾つかのポイントがあります。

グラフのデータを隣接リストの形で保存します
ノードをインデックスとして、該当ノードのout-degreeのエッジの配列を保存します
エッジは、(cost, to)の形で保存します（fromは省略しても構いません）
サイクルができないように、訪問済みのノードはハッシュセットに保存します
エッジはコストの降順で並び替えます（通常ヒープで保存します）
ハッシュセットに保存されているノードがnと達すれば、全てのノードに訪問済みとなり、最小コストが得られます

よって、より詳しいステップは以下となります。

グラフのデータを隣接リストとして保存し、graph[vertex]で該当ノードからのout-degreeエッジの配列を取得する
訪問済みのノードを記録するためのハッシュセットと、エッジをウェイトで並び替えるためのヒープを初期化
1番目のノード0から探索し、ノード0をハッシュセットへ追加、エッジ(0, 0)をヒープへ追加
ヒープにデータが存在する限り下記のループを続ける
- エッジをヒープからポップする
- ハッシュセットに、エッジに記録されているノードが存在する場合はスキップする
- ノードをハッシュセットへ追加し、ウェイトを合計ウェイトへ加える
- ノードをキーとして、グラフ上該当ノードの出次数のエッジをヒープへ追加する
- ハッシュセットがノード合計数と同じになれば、合計ウェイトが最小コストとなる

JSには内蔵のヒープがなく、自前で実装するとかなり面倒なのでここはpythonで例を出します。なお、仮にmin-heapの実装がなく、max-heapの実装となる場合（例えばRust）、マイナスを利用することで一応同じ効果になります。

import heapq
from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, weight, src, dst):
        self.graph[src].append((weight, dst))
        self.graph[dst].append((weight, src))

    def prim_mst(self):
        start_vertex = 0
        visited = set()
        heap = [(0, start_vertex)]  # (cost, vertex)
        total_cost = 0

        while heap:
            cost, vertex = heapq.heappop(heap)
            if vertex in visited:
                continue
            visited.add(vertex)
            total_cost += cost # max-heapの場合は-=costと変える
            for neighbor, edge_cost in self.graph[vertex]:
                if neighbor not in visited:
                    # max-heapの場合は-edge_costをプッシュ
                    heapq.heappush(heap, (edge_cost, neighbor))

        return total_cost

時間複雑度について、ヒープの実装にもよりますが、基本バイナリーヒープの場合は多いでしょう。それで、O(V+E)の時間で全ての頂点を探索する必要があります。さらに、ヒープのポップ操作で都度heapify downが発生し、O(logV)の時間がかかります。総合して、O(V+E)*O(logV)=O(E*logV)となります。空間複雑度について、Vの頂点を保存するためにO(V)となります。

実践問題

Leetcodeの1584. Min Cost to Connect All Pointsで2つのアルゴリズムの解答法をみてみます。

クラスカル法

// UnionFind実装は省略
function minCostConnectPoints(points) {
  const length = points.length;
  const edges = [];

  for (let i = 0; i < length; i++) {
    for (let j = i + 1; j < length; j++) {
      // 全てのポイントをエッジで繋いでいく
      const cost = calcDistance(points[i], points[j]);
      edges.push([cost, i, j]);
    }
  }
  // コストで降順にソート
  edges.sort((a, b) => a[0] - b[0]);
  // UnionFindを初期化
  const dsu = new UnionFind(length);
  let res = 0;
  // 全てのエッジをループし、最小コストのエッジから繋いでいく
  for (const [cost, p1, p2] of edges) {
    if (dsu.find(p1) !== dsu.find(p2)) {
      dsu.union(p1, p2);
      res += cost;
    }
  }

  return res;
}

function calcDistance(p1, p2) {
  return Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
}

プリム法

ここはPythonで例を出します。

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        graph = [[] for _ in range(n)]
        for i in range(n-1):
            for j in range(i+1,n):
                cost = self.cal_distance(points[i], points[j])
                graph[i].append((cost, j))
                graph[j].append((cost, i))
                
        heap = [(0, 0)]
        mst = set()
        total_cost = 0
        while heap:
            cost, vertex = heapq.heappop(heap)
            if vertex in mst:
                continue
            mst.add(vertex)
            total_cost += cost
            for vertex in graph[vertex]:
                heapq.heappush(heap, vertex)
        return total_cost
            
    def cal_distance(self, p1, p2):
        return abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])

まとめ

プリム法とクラスカル法は、どちらも最小全域木を求めるアルゴリズムですが、それぞれのアルゴリズムの特徴と複雑度などをテーブルにまとめました。

項目	プリム法	クラスカル法
アプローチ	貪欲法	貪欲法
基本的な考え方	頂点を追加していく	辺を追加していく
スタート頂点	任意の頂点から開始	なし (辺の重みの昇順に処理)
処理の流れ	既存の頂点集合に隣接する最小コストの辺を選択し、新たな頂点を追加	重みが最小の辺から順に追加し、閉路ができない限り続ける
時間複雑度	`O(V^2)` (隣接行列), `O(E*logV)` (隣接リスト + 優先度付きキュー)	`O(E*logE)`
空間複雑度	`O(V)`	`O(V+E)`
適用可能なグラフ	連結グラフ、無向グラフ	連結グラフ、無向グラフ
最適化のためのデータ構造	ヒープ	Union-Find

今回はMSTについてまとめてみました。次回は単一始点最短経路問題について書きます。

クラスカル法

プリム法

実践問題

クラスカル法

プリム法

まとめ

Discussion