グラフ — 隣接行列 vs 隣接リスト
このトピックを終えると
グラフとは何か、そして隣接行列と隣接リストという2つの表現方法の違いを理解できるようになります。
木はグラフの特殊なケースです
これまで見てきた配列、連結リスト、木 — これらのデータ構造は、データ間の関係が単純です。配列は順序、木は階層です。
しかし、現実の関係は複雑です。SNSでは人々は互いにフォローします。都市は道路でつながっています。ウェブページはリンクでつながっています。このような多対多の関係を表現するデータ構造がグラフです。
グラフは、ノード（または頂点）とノードを接続するエッジで構成されます。木もグラフの一種ですが、「親-子」制約と「サイクルがない」という条件を持つ特殊なグラフです。
有向グラフ vs 無向グラフ
無向グラフ: AとBが接続されている場合、A→B、B→Aの両方向に移動できます。Facebookの友達関係のように、私が友達であれば、相手も友達です。
有向グラフ: A→Bのみ可能で、B→Aはできない場合があります。Instagramのフォローのように、私がフォローしても、相手が私をフォローするとは限りません。
隣接行列：2次元配列
ノードが5個のグラフを5×5の行列で表現します。matrix[i][j] = 1の場合、ノードiからjへのエッジがあることを意味します。
A B C D
A [ 0, 1, 1, 0 ]
B [ 1, 0, 0, 1 ]
C [ 1, 0, 0, 1 ]
D [ 0, 1, 1, 0 ]A-B、A-C、B-D、C-Dが接続された無向グラフです。無向であるため、行列は対角線を基準に左右対称です。
graph = [ [0, 1, 1, 0], [1, 0, 0, 1], [1, 0, 0, 1], [0, 1, 1, 0],]
# AとBが接続されているか確認if graph[0][1] == 1: print("A-B 接続") # O(1)長所: 2つのノードが接続されているかを確認するのが**O(1)**です。インデックスで直接アクセスします。
短所: ノードがN個の場合、N×Nサイズの配列が必要です。ノードが10,000個の場合、1億個のセルが必要です。エッジがあまりなくても、すべての空間を使用します。
隣接リスト：連結リスト
各ノードに対して、「このノードに接続されているノードのリスト」を保存します。
A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]同じグラフですが、表現方法が異なります。
graph = { 'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D'], 'D': ['B', 'C'],}
# Aの隣接ノードを走査for neighbor in graph['A']: print(neighbor) # B, C長所: エッジ数に比例したメモリのみを使用します。ノードが10,000個あっても、エッジが100個の場合、100個分の空間のみが必要です。
短所: 2つのノードが接続されているかを確認するには、リストを走査する必要があります。最悪の場合、**O(N)**です。
どちらを使うべきか
| 隣接行列 | 隣接リスト
---------+------------------+------------------
空間 | O(V^2) | O(V + E)
接続確認 | O(1) | O(degree)
隣接ノード走査 | O(V) | O(degree)
適切な場合 | エッジが多い密なグラフ | エッジが少ない疎なグラフ密なグラフ: ノードに対してエッジが多い。すべての都市間に直行便がある航空ネットワーク。隣接行列が適切です。
疎なグラフ: ノードに対してエッジが少ない。SNSで1億人のユーザーのうち、各ユーザーが平均200人しかフォローしていない。隣接リストが適切です。
ほとんどの実際のグラフは疎なグラフです。そのため、隣接リストが基本的な選択肢です。コーディングテストでも、最初に隣接リストを思いつくとよいでしょう。
重み付きグラフ
エッジに重みを付けることができます。都市間の距離、ネットワークの遅延時間などです。
隣接行列では、1の代わりに重み値を入れます。
# matrix[A][B] = 距離matrix = [ [0, 5, 3, 0], [5, 0, 0, 2], ...]隣接リストでは、タプルで表現します。
graph = { 'A': [('B', 5), ('C', 3)], 'B': [('A', 5), ('D', 2)], ...}重み付きグラフで最短経路を見つけるには、BFSの代わりにダイクストラアルゴリズムを使用します。BFSはエッジ数基準の最短、ダイクストラは重みの合計基準の最短です。
重要なポイント
グラフは、ノードとエッジで多対多の関係を表現するデータ構造です。 隣接行列は、接続確認がO(1)ですが、空間をO(V^2)使用します。 隣接リストは、空間をO(V+E)のみ使用し、ほとんどの実際のグラフで基本的な選択肢です。