第05回 隣接リスト
隣接行列だって無駄が多いじゃないか〜！
はい。その通りです。しかしプログラマーの皆さんは、この程度事なんか全然気にしないのです。余裕のぷっぷくぷーで解決解決。
まあ、タイトルに書いてあるのですが（笑）隣接リストを作れば大幅なメモリの節約が出来そうです。例えば、第01回のグラフを使ってリストを作ってみると
v1: v2 → v5 → 0
v2: v1 → v3 → v4 → 0
v3: v2 → v4 → v5 → 0
v4: v2 → v3 → v5 → 0
v5: v1 → v3 → v4 → 0
(0でおしまい)
こんなかんじで表すことができます。
また、このグラフは無向グラフなので、v1→v2とv2→v1を同じものとして片方省くと、
v1: v2 → v5 → 0
v2: v3 → v4 → 0
v3: v4 → v5 → 0
v4: v5 → 0
v5: 0
という風にさらに小さいリストで表すこともできます。小さなグラフなのであまりピンと来ないかもしれませんがグラフが大きくなればなるほど効果的です。
というわけで、隣接行列でも隣接リストを作ればそれなりのプログラムは書けそうですね。こんなんばっかり書いているのも飽きてきたので、ボチボチプログラムでも書いてみましょうか。。。
つづく
