グラフのパス存在判定

着いているのに、まだ歩き回っている

前の 2 つのレッスンでは、届く範囲を最後まで塗りつぶしました。今回知りたいのは 1 つだけです。「s から t へたどり着けるか」。

範囲を全部塗ってから t が入っているかを調べても答えは出ます。ただ、点が 100 万あって t が s の隣にいる場合でも、100 万点を歩き終えてから答えることになります。

t を見つけた瞬間に打ち切る。それだけで、多くの場合の探索が一瞬で終わります。

この「着けるか」は現場でもよく出てきます。この設定ファイルは間接的にでもあのモジュールを読み込んでいるか。この権限はどこかの継承をたどって管理者につながっていないか。どれも同じ問いです。

見つけたら、その場で返す

打ち切りは特別な技法ではありません。ふつうの探索でも同じことをしています。

最後まで回してから真偽値を組み立てるのではなく、条件に合ったところで return してしまう。グラフでも同じで、隣を見ている途中で t が出てきたら、キューに入れずにその場で返します。

判定を置く場所は 2 通りあります。キューから取り出したときに見るか、隣として見つけたときに見るか。どちらでも答えは同じですが、後者のほうが 1 歩ぶん早く終わります。

打ち切らずに最後まで回しても答えは合うので、遅いことに気づきにくいのがこの間違いの厄介なところです。

なお、この問題ではキューでもスタックでもかまいません。知りたいのは「着けるかどうか」だけで、どの順で着いたかも、何歩で着いたかも問われないからです。順番を選ぶ必要があるのは、順番そのものが答えに関わるときだけです。

再帰で書く場合は、隣に潜った結果が真なら自分も真を返す、というバケツリレーの形になります。1 つでも真が返ってきた時点で、残りの隣は見なくてよい点は同じです。

出発点と目的地が同じとき

見落としやすいのが、s と t が同じ場合です。1 歩も動かなくてよいので答えは真ですが、素直に書くと偽が返ります。

理由は順番にあります。探索を始めるとき、s を訪問済みにしてからループへ入ります。その後 s の隣を見ていっても、s 自身はすでに訪問済みなので候補に上がらず、t には二度と出会えません。

ですから、探索を始める前に「出発点と目的地が同じなら真」を先に返してしまいます。テストにもこの形が入っています。

やってみよう

• edges=[[0,1],[1,2],[2,3]] で 0 から 3 へは真になる
• 2 つの塊に分かれた edges=[[0,1],[2,3]] で、0 から 3 へは偽になる
• 辺が 1 本もない状態で、出発点と目的地を同じにすると真になる
• edges=[[0,1],[1,2],[2,0],[2,3]] のように輪を含む形でも、3 へ着けることを確かめる

1. BFS または DFS で実装すること
2. t を見つけたら直ちに True を返して打ち切ること
3. s == t の場合は True を返すこと