Skip to content

README.md

Latest commit

 

History

History
233 lines (158 loc) · 5.64 KB

README.md

File metadata and controls

233 lines (158 loc) · 5.64 KB

グラフ（Graph）のデータ構造は、ノード（頂点, Vertex）とエッジ（辺, Edge）で構成されるデータ構造であり、多くのアルゴリズムやアプリケーションで利用されます。ここでは、グラフの基本的な概念、表現方法、種類、関連アルゴリズムについて詳しく説明します。

1. グラフの基本概念

(1) グラフの定義

グラフ ( G ) は、以下のように定義されます：

  • ( G = (V, E) )
    • ( V ) : 頂点（ノード）の集合
    • ( E ) : 辺（エッジ）の集合（頂点のペア）

エッジは2つの頂点を接続するもので、以下のように分類されます：

  • 無向グラフ（Undirected Graph）: エッジが方向を持たない
  • 有向グラフ（Directed Graph, Digraph）: エッジが一方通行（方向を持つ）

2. グラフの表現方法

グラフのデータを表現する方法にはいくつかの選択肢があります。

(1) 隣接行列（Adjacency Matrix）

  • ( N \times N ) の行列 ( A ) を使い、エッジの有無を示す
  • 無向グラフでは対称行列になる
  • 有向グラフでは非対称になることがある

例（無向グラフ）

[ A[i][j] = \begin{cases} 1 & (i, j) \text{ 間にエッジがある} \ 0 & \text{それ以外} \end{cases} ]

メリット:

  • エッジの有無を ( O(1) ) で確認できる
  • 行列演算を利用したアルゴリズムが実装しやすい

デメリット:

  • ( O(N^2) ) の空間を消費（疎なグラフには不向き）

(2) 隣接リスト（Adjacency List）

各頂点に対して、その頂点と接続されている頂点のリストを保持する。

実装例（Python）

graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 4],
    3: [1, 5],
    4: [1, 2, 5],
    5: [3, 4]
}

メリット:

  • メモリ使用量が ( O(V + E) ) と効率的
  • 隣接するノードを列挙するのが容易

デメリット:

  • エッジの存在チェックが ( O(\deg(v)) ) で遅い（行列の ( O(1) ) に比べると不利）

(3) エッジリスト（Edge List）

エッジをリストとして格納する方法。

例

edges = [
    (0, 1),
    (0, 2),
    (1, 3),
    (1, 4),
    (2, 4),
    (3, 5),
    (4, 5)
]

メリット:

  • メモリ効率が良い
  • エッジを1つずつ処理するアルゴリズム（クラスター分析など）に向いている

デメリット:

  • エッジの探索が遅い
  • 特定のノードの隣接リストを取得するのが面倒

3. グラフの種類

(1) 無向グラフ（Undirected Graph）

エッジが双方向のグラフ。

例

A — B
|   |
C — D
  • エッジ (A, B) は (B, A) と同じ

(2) 有向グラフ（Directed Graph, DAG）

エッジが一方向のグラフ。

例

A → B → C
↓
D → E
  • DAG（Directed Acyclic Graph）: サイクルがない有向グラフ（例: タスク依存関係の管理）

(3) 重み付きグラフ（Weighted Graph）

エッジにコスト（重み）がついたグラフ。

例（Pythonの辞書で表現）

graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'C': 5, 'D': 10},
    'C': {'D': 3},
    'D': {}
}
  • ダイクストラ法（Dijkstra's Algorithm） や ベルマンフォード法（Bellman-Ford Algorithm） で最短経路を求める

4. グラフのアルゴリズム

(1) グラフ探索

  • 深さ優先探索（DFS）

    • 再帰またはスタックを利用
    • 実装例 
      def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

  • 幅優先探索（BFS）

    • キューを利用

    • 実装例

      from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            queue.extend(graph[node])
    return visited

(2) 最短経路探索

  • ダイクストラ法（Dijkstra's Algorithm）

    • ヒープ（優先度付きキュー）を利用して最短経路を求める
    • ユーザーの興味があるヒープベースの優先度付きキューを活用可能

  • ベルマンフォード法（Bellman-Ford Algorithm）

    • 負の重みを持つグラフにも対応

(3) 最小全域木（MST）

  • クラスカル法（Kruskal's Algorithm）
    • エッジリストをソートし、**Union-Find（Disjoint Set）**を使ってMSTを構築
  • プリム法（Prim's Algorithm）
    • 優先度付きキュー（ヒープ）を活用

5. グラフの応用

  • ネットワークルーティング（例: Dijkstra）
  • タスクスケジューリング（例: DAG）
  • ソーシャルネットワーク分析（例: BFS, DFS）
  • 交通システム（例: 最短経路）

まとめ

グラフはさまざまな方法で表現でき、用途に応じたデータ構造とアルゴリズムを選ぶことが重要です。特に、ヒープを使った優先度付きキューは、DijkstraやPrimのアルゴリズムで活躍する