グラフ

グラフの問題では、最初に有向・無向、重みの有無、連結性を確認する。対象が木なら 木の走査 のように親を記録するだけで扱える場合が多い。

二頂点間や単一始点からの距離が必要な問題は 最短経路 へ進む。辺重みによって使えるアルゴリズムが変わるため、実装より先に入力条件を分類する。

一般のグラフを走査するだけなら BFS または DFS を使う。重み付きグラフでは、距離の確定順序を管理する必要がある。