グラフアルゴリズム入門 : 最小全域木 (MST)

## はじめに
この記事では、**最小全域木 (Minimum Spanning Tree, MST)** の概念と理論、具体的なアルゴリズム (Kruskal/Prim) を解説します。また、Python の **NetworkX** ライブラリを用いた実装例を紹介し、Google Colab 上で簡単に実行可能なサンプルコードを提供します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2648069/35d0b14a-af89-1788-a31a-a52f1abbd773.png)

---

## 1. 最小全域木とは？

### 定義
- **全域木 (Spanning Tree)**: グラフの全ての頂点を繋げるが、閉路 (サイクル) を含まない部分グラフ。
- **最小全域木 (MST)**: 全域木の中で、エッジの重みの合計が最小となるもの。

### 応用例
- **ネットワーク設計**: ケーブルの長さやコストを最小限に抑えた配線計画。
- **クラスタリング**: 最も長いエッジをカットしてクラスタを分ける手法。
- **画像セグメンテーション**: 画像をグラフとして扱い、セグメント化を行う。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2648069/4d48cd7f-031b-7ebe-532e-b8dc928c37bf.png)

---

## 2. MST を求めるアルゴリズム

### 2.1 Kruskal アルゴリズム
1. 全てのエッジを重みの小さい順にソートする。
2. 順にエッジを取り出し、閉路ができない場合に採用する。
3. エッジ数が \( V-1 \) 本になるまで続ける。

#### 計算量:
\( O(E \log E) \) (エッジのソートがボトルネック)。

### 2.2 Prim アルゴリズム
1. 任意の頂点を選び、木 (MST) を開始する。
2. 現在の木に接続可能な最小重みのエッジを選ぶ。
3. 全ての頂点が含まれるまで繰り返す。

#### 計算量:
\( O(E \log V) \) (優先度付きキューを用いる場合)。


![mst-algorithms.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2648069/8922db2d-501f-203b-9bc7-6ae989387553.png)

---

## 3. NetworkX を使った実装例

以下のコードは Python の **NetworkX** を使って MST を求める例です。Google Colab などでコピー＆ペーストして実行できます。

```python
# Install necessary libraries (if running on Google Colab)
!pip install networkx matplotlib

# Import libraries
import networkx as nx
import matplotlib.pyplot as plt

# Create a graph
G = nx.Graph()

# Add nodes and weighted edges
G.add_edges_from([
    ("A", "B", 4), ("A", "C", 2), ("B", "C", 1), 
    ("B", "D", 5), ("C", "D", 8), ("C", "E", 10), ("D", "E", 2)
])

# MST の計算
# デフォルトでは Kruskal アルゴリズムが使用されます
mst = nx.minimum_spanning_tree(G)

# Prim アルゴリズムを使用する場合は以下のいずれかを使用します
# mst = nx.minimum_spanning_tree(G, algorithm='prim')

# Print edges in the MST
print("Edges in the MST:", list(mst.edges(data=True)))

# Visualize the graph and MST
pos = nx.spring_layout(G, seed=42)
plt.figure(figsize=(8, 6))

# Draw the original graph
nx.draw(G, pos, with_labels=True, node_color='lightblue', edge_color='gray', node_size=800)
nx.draw_networkx_edge_labels(G, pos, edge_labels=nx.get_edge_attributes(G, 'weight'))

# Highlight the MST edges
nx.draw_networkx_edges(G, pos, edgelist=mst.edges, edge_color='red', width=2)
plt.title("Minimum Spanning Tree (MST)")
plt.show()
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2648069/72d024c5-857a-1a25-5ebe-f3ba2efc8a3d.png)

---

## 4. まとめ

- 最小全域木 (MST) は、ネットワーク設計やクラスタリングなど、様々な応用が可能な重要な概念です。
- Kruskal アルゴリズムと Prim アルゴリズムは MST を効率的に求める手法として広く使われています。
- Python の **NetworkX** ライブラリを活用すると、MST の計算と可視化が簡単に行えます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2648069/2c20784b-aba4-f254-c342-6c758b295336.png)

---

## 参考文献
- [NetworkX ドキュメント](https://networkx.org/documentation/stable/)
- [Prim アルゴリズム (Wikipedia)](https://ja.wikipedia.org/wiki/プリムのアルゴリズム)

## 実装例: ノートブック

```json

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c9b2b726",
   "metadata": {},
   "source": [
    "# Minimum Spanning Tree (MST) Example with NetworkX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5f0dd9ad",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# Install necessary libraries (if running on Google Colab)\n",
    "!pip install networkx matplotlib\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "88c0d7be",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# Import libraries\n",
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# Create a Graph object\n",
    "G = nx.Graph()\n",
    "\n",
    "# Add nodes (labeled in English letters)\n",
    "G.add_nodes_from([\"A\", \"B\", \"C\", \"D\", \"E\"])\n",
    "\n",
    "# Define edges as (node1, node2, weight)\n",
    "edges = [\n",
    "    (\"A\", \"B\", 4),\n",
    "    (\"A\", \"C\", 2),\n",
    "    (\"B\", \"C\", 1),\n",
    "    (\"B\", \"D\", 5),\n",
    "    (\"C\", \"D\", 8),\n",
    "    (\"C\", \"E\", 10),\n",
    "    (\"D\", \"E\", 2)\n",
    "]\n",
    "\n",
    "# Add edges with weights\n",
    "for u, v, w in edges:\n",
    "    G.add_edge(u, v, weight=w)\n",
    "\n",
    "# Calculate the Minimum Spanning Tree\n",
    "mst = nx.minimum_spanning_tree(G)\n",
    "\n",
    "# Extract edges from MST\n",
    "mst_edges = list(mst.edges(data=True))\n",
    "print(\"Edges in the MST:\", mst_edges)\n",
    "\n",
    "# Draw the original graph and MST\n",
    "pos = nx.spring_layout(G, seed=42)\n",
    "plt.figure(figsize=(8,6))\n",
    "\n",
    "# Draw the original graph in gray\n",
    "nx.draw_networkx(\n",
    "    G, pos, \n",
    "    node_color='lightblue', \n",
    "    edge_color='gray',\n",
    "    with_labels=True,\n",
    "    node_size=800\n",
    ")\n",
    "\n",
    "# Highlight MST edges in red\n",
    "mst_edge_list = [(u, v) for (u, v, d) in mst_edges]\n",
    "nx.draw_networkx_edges(G, pos, edgelist=mst_edge_list, edge_color='red', width=2)\n",
    "\n",
    "# Show edge weights\n",
    "edge_labels = {(u, v): d['weight'] for (u, v, d) in G.edges(data=True)}\n",
    "nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)\n",
    "\n",
    "plt.title(\"MST (Red edges represent the Minimum Spanning Tree)\")\n",
    "plt.axis('off')\n",
    "plt.show()\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 5
}
```