一覧CS-06-4 · 木・ハッシュ・グラフの構造

グラフの隣接リストと隣接行列

同じ接続関係を二つの形式で表し、辺の追加と検索方法を学びます。

説明

グラフは頂点と辺で接続関係を表します。例えばAからBへ進める関係を有向辺A→Bで表します。隣接リストは各頂点から出る接続先を列挙し、隣接行列は出発点を行、到着点を列とする表に辺の有無を記録します。

4頂点の同じグラフを両形式で作成します。Aから出る辺、Cに入る辺、接続の追加を調べ、必要な記録数を比較します。最後に向きを持たない辺へ変えたとき、行列が対称になることを確かめます。

1頂点と有向辺

頂点A・B・C・Dを用意し、A→B、A→C、B→C、C→Dを接続します。順序付きの組では前が出発点、後ろが到着点です。

vertices = ['A', 'B', 'C', 'D']頂点の順序; edges = [('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'D')]出発点と到着点; vertices, edges頂点と辺

AからCへは直接進めます。CからAへ進めるとは限りません。有向辺では向きが意味を持つため、逆向きは別の辺として記録します。

2接続先を頂点ごとに列挙

各頂点から出る辺の到着点を集めます。出る辺のないDにも空のリストを用意します。

adj = {v: [end for start, end in edges if start == v] for v in vertices}出発点ごとに到着点を収集; adj隣接リスト

AはB・C、BはC、CはD、Dは空です。頂点から出る辺を列挙するとき、その頂点のリストだけを取得できます。孤立点や出口のない頂点も省略せず表現できます。

3行と列で接続を表す

同じ頂点順で4×4の行列を作ります。辺があれば1、なければ0です。行は出発点、列は到着点という約束を固定します。

matrix = [[int((start, end) in edges) for end in vertices] for start in vertices]辺の有無を0・1へ; print(' ' + ' '.join(vertices))列名; print('\n'.join(v + ' ' + ' '.join(map(str, row)) for v, row in zip(vertices, matrix)))行名と各行

A行のB列とC列が1です。C行のA列は0なので、A→CとC→Aを取り違えないように読みます。自己ループがないため対角成分は全て0です。

4Aから出る辺を取得

A行で1の列を拾う方法と、隣接リストを直接取得する方法を比べます。どちらも同じ接続先を返します。

adj['A']Aの隣接リスト, [vertices[i] for i, present in enumerate(matrix[0]) if present]A行の1を抽出

いずれもB・Cです。行列ではAの行を走査します。隣接リストではAに登録した接続先だけを列挙します。

5Cへ入る辺を取得

到着点がCの辺を調べます。行列ならC列、隣接リストなら各頂点のリスト内を調べます。

[v for v in vertices if 'C' in adj[v]]各リストにCがあるか, [vertices[i] for i in range(len(vertices)) if matrix[i][2]]C列の1を抽出

AとBからCへ入ります。出る辺を持つ隣接リストで入る辺も頻繁に調べたい場合は、逆向きの隣接リストを別に持つ方法があります。

6DからAへの辺を追加

Dの接続先へAを加え、行列のD行A列も1にします。一方だけ更新すると同じグラフを表せなくなります。

adj['D'].append('A')リストへ追加; matrix[3][0] = 1行列へ追加; adj['D'], matrix[3]変更した行, all(matrix[i][j] == int(end in adj[start]) for i, start in enumerate(vertices) for j, end in enumerate(vertices))全接続の一致を検査

DのリストはA、D行は1・0・0・0です。全組の照合結果はTrueで、両形式が一致しています。A→C→D→Aという閉路もできました。

7記録する項目数

行列は辺の有無にかかわらず頂点数の2乗の枠を持ちます。隣接リストは各頂点の管理情報に加えて、辺の分だけ接続先を記録します。

len(vertices)**2行列の枠数, sum(len(neighbors) for neighbors in adj.values())接続先の総数, len(vertices)頂点管理の個数

行列は16枠、隣接リストの接続先は5件、頂点は4個です。実際のバイト数は実装に依存しますが、辺が少ない大きなグラフでは枠数の差が広がります。

8無向辺では逆向きも存在

各接続を両方向にすると、行列は対称になります。ここでは行列の転置側とのORを取って両方向へ広げます。

undirected = [[int(matrix[i][j] or matrix[j][i]) for j in range(4)] for i in range(4)]逆方向も接続; undirected無向グラフの行列, all(undirected[i][j] == undirected[j][i] for i in range(4) for j in range(4))対称性を検査

対称性の検査はTrueです。無向グラフの辺を隣接リストで持つ場合も両側へ登録します。自己ループを除く辺なら、接続先の登録数は辺数の2倍になります。

まとめ

隣接リストと隣接行列は同じ辺を異なる配置で表します。行列の行・列の向きを固定して扱います。

辺の追加後は、接続先だけでなく逆向きや全表現との一致も確認できます。

行列は頂点数の2乗、隣接リストは頂点数と辺数に応じた領域を使います。

操作履歴と解説を振り返れます。

Python 3

1
vertices = ['A', 'B', 'C', 'D']; edges = [('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'D')]; vertices, edges
(['A', 'B', 'C', 'D'], [('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'D')])
2
adj = {v: [end for start, end in edges if start == v] for v in vertices}; adj
{'A': ['B', 'C'], 'B': ['C'], 'C': ['D'], 'D': []}
3
matrix = [[int((start, end) in edges) for end in vertices] for start in vertices]; print(' ' + ' '.join(vertices)); print('\n'.join(v + ' ' + ' '.join(map(str, row)) for v, row in zip(vertices, matrix)))
  A B C D
A 0 1 1 0
B 0 0 1 0
C 0 0 0 1
D 0 0 0 0
4
adj['A'], [vertices[i] for i, present in enumerate(matrix[0]) if present]
(['B', 'C'], ['B', 'C'])
5
[v for v in vertices if 'C' in adj[v]], [vertices[i] for i in range(len(vertices)) if matrix[i][2]]
(['A', 'B'], ['A', 'B'])
6
adj['D'].append('A'); matrix[3][0] = 1; adj['D'], matrix[3], all(matrix[i][j] == int(end in adj[start]) for i, start in enumerate(vertices) for j, end in enumerate(vertices))
(['A'], [1, 0, 0, 0], True)
7
len(vertices)**2, sum(len(neighbors) for neighbors in adj.values()), len(vertices)
(16, 5, 4)
8
undirected = [[int(matrix[i][j] or matrix[j][i]) for j in range(4)] for i in range(4)]; undirected, all(undirected[i][j] == undirected[j][i] for i in range(4) for j in range(4))
([[0, 1, 1, 1], [1, 0, 1, 0], [1, 1, 0, 1], [1, 0, 1, 0]], True)

演習完了