グラフDFSについてのまとめ

今回はDFSのまとめです。グラフにおけるDFSではどのようなことを行えるのかまとめました。

↓今までのグラフに関する記事
（初心者向け）グラフの実装について - bplain’s blog
（初級者競プロer向け）グラフの探索(DFS)を1から再帰関数で実装する方法 - bplain’s blog
（初級者競プロer向け) グラフDFS問題編その１ - bplain’s blog
グラフDFS問題編その２ (ABC087-D) - bplain’s blog
グラフDFS問題編その３ (ABC075-C) - bplain’s blog

今回はまとめですので、いきなりですが結論に入ります。

DFSで出来ること

１、各頂点にとある1点からの距離を置ける。(引数にdist、配列にd[i]の使用）
２、とある1点と連結している頂点を探せる。(配列visited[i]の使用）
３、全ての頂点からDFSを行うことにより、DFS開始の頂点の番号を、その頂点に連結している全ての頂点に書くことが出来る。(par[i]=startv)

といった感じです。正直ここまで書いておいて何ですが、これらはunion-findで内部に実装可能です。
ただ、こういった場面ではDFS特有の強さを誇れそうです。

４、各頂点に固有の特徴を付けることが出来る（一つ前の頂点を引数に用いることが可能なため）
例題：D - 辺彩色（これはアルゴリズムの難易度が高く紹介しきれませんでした。解説の方をご覧あれ。）

また、各頂点に特有のbitを立て、組み合わせの確認用のマスクビットを作り、それによりその頂点の状況、またその頂点付近の状況を判断する。
果たしてどういった問題に適用できるか分かりませんが、何か問題に使えそうな気がします。

要点はこんなところでしょうか。実装についてもまとめようと思ったのですが、取り上げた問題の中でほぼ要所を書いてしまっている気がしたので、その３つの記事を見比べした方が分かりやすそうです。まだ感覚のつかめない方は是非見比べてみてください。あるいはtwitterで質問でも送ってください。

おわりに

グラフDFSについての内容は以上となります。恐らくですがほとんど網羅したのではないでしょうか。
次回からはunion-find編となります。ここまで読んだ方であればunion-findの中身は簡単に理解できると思うので、よく使われる実装の形についてまた書いていこうと思います。今回はここまで。

あとがき

自分の中では初めての長い記事となりました。今回の記事をまとめるにあたって、取り上げやすい問題を探したり、また解説を見たりと色々行いました。その際、色々探したつもりではあるのですが、グラフDFSの実装に気を使った記事は見当たらなかったので、その部分を埋めることはできたかなと思っています。
自分はアルゴリズムの方は理解するのが楽しいのですが、実際に問題に対してどう実装するのかといった部分が少し苦手です。そういった人のために記事を書けるよう頑張っていきたいです。