グラフの表現方法（隣接リストと隣接行列）

グラフは、ノード（頂点）とそれらを結ぶエッジ（辺）から構成されるデータ構造です。Pythonを使ってグラフを表現する際には、主に2つの方法があります: 隣接リストと隣接行列です。それぞれの表現方法には利点と欠点がありますので、ここではそれらを詳しく見ていきます。

隣接リスト

隣接リストは、各ノードに対して、そのノードから出るエッジのリストを保持するデータ構造です。一般的には、Pythonのリストや辞書を使用して実装します。

実装例

以下のコードは、隣接リストを使用して無向グラフを表現する例です。

class Graph:
    def __init__(self):
        self.adjacency_list = {}

    def add_edge(self, u, v):
        if u not in self.adjacency_list:
            self.adjacency_list[u] = []
        if v not in self.adjacency_list:
            self.adjacency_list[v] = []
        self.adjacency_list[u].append(v)
        self.adjacency_list[v].append(u)

    def display(self):
        for node, edges in self.adjacency_list.items():
            print(f"{node}: {', '.join(map(str, edges))}")

# グラフのインスタンスを作成
graph = Graph()
# エッジを追加
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 4)
graph.add_edge(3, 4)

# グラフを表示
graph.display()

コード解説

1. Graphクラスの定義: グラフを表現するクラスを定義します。
2. __init__メソッド: 空の隣接リストを初期化します。これは辞書として実装されます。
3. add_edgeメソッド: 無向エッジを追加するメソッドです。ノードが存在しない場合は新たにリストを初期化し、エッジを追加します。
4. displayメソッド: グラフの隣接リストを表示します。

隣接行列

隣接行列は、ノードの数に応じた2次元配列（リストのリスト）を使用して、各ノード間の接続を表します。行列の要素は、エッジが存在する場合は1（またはエッジの重み）、存在しない場合は0となります。

実装例

以下のコードは、隣接行列を使用して無向グラフを表現する例です。

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adjacency_matrix = [[0] * num_vertices for _ in range(num_vertices)]

    def add_edge(self, u, v):
        self.adjacency_matrix[u][v] = 1
        self.adjacency_matrix[v][u] = 1

    def display(self):
        for row in self.adjacency_matrix:
            print(' '.join(map(str, row)))

# グラフのインスタンスを作成（4つの頂点）
graph = Graph(4)
# エッジを追加
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 3)

# グラフを表示
graph.display()

コード解説

1. Graphクラスの定義: グラフを表現するクラスを定義します。
2. __init__メソッド: ノード数を受け取り、対応するサイズの隣接行列を初期化します。
3. add_edgeメソッド: 無向エッジを追加するメソッドです。行列の対応する要素を1に設定します。
4. displayメソッド: 隣接行列を表示します。

隣接リストと隣接行列の比較

• メモリ使用量:

  • 隣接リスト: エッジの数に応じたメモリを使用し、スパースグラフに適しています。
  • 隣接行列: ノード数の二乗のメモリを使用し、完全グラフや密なグラフに適しています。

• エッジの追加/削除の効率:

  • 隣接リスト: O(1)でエッジを追加できますが、削除にはO(V)の時間がかかることがあります。
  • 隣接行列: O(1)でエッジの存在を確認できますが、エッジの追加や削除もO(1)です。

• 探索の効率:

  • 隣接リスト: エッジ数に依存するため、探索にかかる時間はO(E)です。
  • 隣接行列: O(V)で全ノードの接続を確認できますが、エッジ数が少ない場合には効率が悪くなります。

これらの情報を基に、必要に応じて適切な表現方法を選択してください。どちらの方法も特定の状況で有用ですので、状況に応じて使い分けることが大切です。