グラフが苦手

GCJ の問題を解いていると、やっぱりグラフが苦手ということを感じるので『アルゴリズムC』のグラフアルゴリズムの部分を眺めたりしました。

それで思ったことはいくつかあるのですが、アルゴリズムがどのようなコードで実現されるのかが見えていないという点が一つの大きな障害になっているような気がしました。グラフというと普通は平面上の点と点を線で結んだようなものを想像しますが、そのイメージがプログラムのどんなソースコードとも結びつかないような感じです。

とりあえず(他はよく知らないので)アルゴリズム系のコンテストなどの問題を想定しての話になりますが、実際にアルゴリズムを実装するときには、頂点と辺がそれぞれオブジェクトとして存在していることは稀ではないかと思うのです。普通はせいぜい整数あるいはその他何らかの特徴的なデータをもって代えることが多く、対応するデータが計算機上には存在しないことも少なくない気がします。無限個の頂点を持つグラフを扱うような問題はそういう例になるでしょう (例えば今年の GCJ の Round 1A, Problem B)。

だとすれば、実際にグラフアルゴリズムを使って問題を解くプログラムは、教科書に載っているような例とはわりと違った見た目になるんじゃないかという気がするのです。それがたとえ(よく理解している人にとっては)基本的なアルゴリズムを適用しただけのものであっても、少なくとも慣れないうちはそうなんじゃないかと思います。教科書で示しているのはあくまでも基本的な骨格の部分だけで、大枠は教科書と同様にやって細かいところはその都度自分で埋めるということになるのでしょう。

わかってしまえばそんなにたいしたことではないのかもしれませんが、最初はそういうことに気付けないでいたようです。グラフアルゴリズムを適用するには、まずあの平面に描かれたグラフと同じ構造をもったものを計算機上に作らなければならないと以前は思っていたような気がします。隣接行列のような表現方法も、存在は知っていましたが計算機上でそれを使うという発想は持っていませんでした。さらにいえば、実際にはグラフの直接的な表現を作ることすら必要ない(こともある)ようで、これに気付いたときは「なんだ、そうだったのか」と思いました。

教科書的な一般論は、直接適用するためにあるのではなく、コードを書く指針とするためのものだと考えたほうがよいのかもしれません。

最近、そんなことを思い始めました。