競技プログラミングの文脈における「グラフを陽に持つ」という表現について

書いた人: allegrogiken

カテゴリ: competitive_programming

AtCoderなどのグラフ問題の解説において「グラフを陽に持たずに〜しましょう」といった表現に遭遇することがあります。 この表現は稀に登場しますが、具体的な解説をウェブ上で見つけることができませんでした。 私なりの理解をこの記事で表現してみようと思います。

グラフを陽に持つ実装の例

例えば、グラフを隣接行列や隣接リストとして2次元配列で表現する場合を考えます。 これはグラフの実体を2次元配列として具現化していることになり、これは「陽に持つ」実装と言えます。

グラフを陽に持たない実装の例

例えば、N*N の正方形上のマス目を左上から右下に移動する・・ というようなシナリオを考えます。 とあるマスからは右、あるいは下にだけ移動することができます。

こういったマス目上の実装をする場合、マスごとの情報を2次元配列に持つと思います。これは「頂点」を表しています。 「辺」についてはどうでしょうか。これは頂点番号(x, y)から明らかであるので、辺のためのデータは作らないと思います。

こういったケースが「陽に持たずに」遷移を実装していると言えます。