わかりやすく BFS DFS とは

一つの点から出発

前のレッスンでグラフを見ました。点はノード、線はエッジで、輪のないグラフがツリーでした。
今度はその上を歩いてみます。歩くには、まずどこから出発するかを決めなければなりません。
点を一つ選ぶと、すぐつながった隣から目に入ってきます。

点を押して出発点を決めます。（出発点 = 青 · すぐつながった隣 = 明るく）

出発点から一歩進むと隣に着き、そこからもう一歩進むと隣の隣です。
こうして線に沿って足を運び、点を一つずつ踏んでいくのが、グラフの上を歩くということです。

近い順、幅優先

一つ目の歩き方は波です。出発点のすぐそばを全部踏み、次に一層遠く、さらに一層遠くへ進みます。
池に石を投げると輪が広がるように、近いところから順に外へ広がっていきます。

押すたびに、一層ずつ波のように広がります。（踏んだ点 = 色 · 同じ層は同じ距離）

波が広がるあいだ、まだ行っていない点は待ちの列に並びます。先に列に並んだ点から順に立ち寄ります。
だから近い点は、いつも遠い点より先です。層がそのまま距離なのです。

最後まで、深さ優先

二つ目の歩き方は迷路の探検です。一本の道を選んで、行けるところまでずっと進みます。
もう行く先がなければ一歩戻って、まだ行っていないわき道へまたずっと進みます。
広く広がるかわりに、深く掘り下げるのです。

押すたびに一本の道を最後まで進み、行き止まりなら戻ります。（今の点 = 青 · 戻った道 = 薄く）

戻る場所を忘れないように、通ってきた点を積んでおきます。
積んだ山のいちばん上からたどり直して、わき道を探します。だから深さ優先は、いちばん最近立ち寄ったところへ先に戻るのです。

幅優先は最短をくれる

波はただ広がるわけではありません。近い層から踏むので、ある点に初めて着いた瞬間が、そのままいちばん速い道です。
線の長さがどれも同じなら、何層目で着いたかが、そのまま出発点からの距離になり、回り道はありません。

点を押すと、二つの歩き方の到着距離を比べられます。（幅優先の層の番号 = そのまま最短距離）

深さ優先は速く遠くまで行きますが、回り道をして着くこともあります。だから最短距離は、波、つまり幅優先の役目です。
ただし今は、すべての線の長さが同じだと考えました。線ごとに長さが違うと話は変わりますが、それは次のレッスンで扱います。

まとめ

グラフの上を歩く二つの方法を見ました。幅優先は波のように近いところから一層ずつ広がり、深さ優先は一本の道を最後まで進んでから戻ってきます。
どちらもすべての点を踏みますが、順番が違います。距離が同じなら、幅優先が最短です。

二つの歩き方を押すと、それぞれの形が現れます。（幅優先 = 波 · 深さ優先 = 最後まで）

地図で道を探す、友だちの友だちをたどる、迷路から抜け出す。グラフの上を歩くことは、思ったより身近にあります。
次のレッスンでは、線ごとに長さが違うグラフで、いちばん速い道を探します。