03.md

実装コラム　グラフの表現

コラム一覧に戻る

最終更新日：2023/03/22

導入

競技プログラミングでほぼ暗黙の了解となっている、「グラフは隣接リストで表現する」という実装方法（もちろん、問題によっては例外あり）。各頂点 $v$ について、それに隣接する頂点あるいは辺を列挙することで、グラフの高速な探索を可能にします。各頂点にリストがあるので、素直に実装すると「リストのリスト」が生じることになります。

ライブラリでは可能な限り高速化したいものです。「リストのリスト」において、例えば vector<vector<int>> などを構築しようものなら、各 vector でアクセスするメモリは別々に確保され、メモリの使用効率やアクセス効率が悪化してしまいます。改善方法がいくつかありますが、グラフの形が変わらない場合、 $1$ つのリストにすべてのリストを連結したものを構築し、適当なポインタと同時に管理することで同様のアクセスを行うのがとても効率的です。グラフの形が変わらない場合はぜひこの形式を使用したいものです。

このため、私のライブラリでは CsrArray<T> 型を採用しました。これは T 型の要素をもつ「リストのリスト」に関して、各リストの長さが変化しないという条件のもと各要素に番号でアクセスする機能を提供します。

ただし、このようなリストだけでは柔軟なグラフの変形は実装が難しくなりますし、また、例えば CsrArray<int> が与えられたとしてそのリストが「各頂点に隣接する頂点のリスト」なのか「各頂点から出る辺の番号のリスト」なのか、うまく表現できません。そのため、私はライブラリに辺を単純にリストで管理するクラスを追加しました。

Graph 構造体は vector<Edge> の代替のような実装になっています。 Edge は両端の頂点の組です。 Graph 構造体は頂点の個数で初期化でき、辺を動的に追加したり、各辺を編集したりできます。さらに、ここで CsrArray<T> を出力する関数を用意して、「リストのリスト」を効率的に、目的を確認できるソースコードで構築できるようにしました。

グラフライブラリについて

このライブラリでは、グラフは主に Graph または CsrArray<int> で表現することにしています。辺に重みがある場合は、 Graph （すなわち辺のリスト）と要素番号を合わせた別のリストを使用します。グラフが有向か無向かは Graph の構築時に設定できるほか、 Graph から CsrArray<int> を構築するときにも改めて設定できます。通常、 Graph から CsrArray<int> に変換してからアルゴリズムを実装します。たいていのアルゴリズムはグラフ全体を探索しますから、計算量の増加は定数倍の範囲です。

ライブラリを使用したい場合において、シンプルな実装をしたい場合、ユーザーは Graph のみ扱って CsrArray<int> を扱う必要がありません。逆に、実装の単純化よりも高速化を図りたい場合、時によって CsrArray<int> を保存することができます。ライブラリは（現状できてないけど） Graph でも CsrArray<int> でもグラフを入力できるようにするので、用途に応じて使い分けることができます。

---

TOP PAGE

<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax:{inlineMath:[['\$','\$']],processEscapes:true},CommonHTML: {matchFontHeight:false}});</script> <script type="text/javascript" async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-MML-AM_CHTML"></script>