スポンサーリンク

隣接リスト

隣接リスト

今回は、上記の経路(有向グラフ)を、隣接リストで表現します。

スポンサーリンク

深さ優先探索

深さ優先探索は、行き止まりに到達するまで、先に先に経路を進めるイメージです。
再起を使うとシンプルに書けてしまいます。

dfs()の引数で、スタート地点とゴール地点を設定します。
通過した地点は、配列route[地点]の要素に1を代入します。
ゴール地点まで到達したら、Found targetと表示します。
あとは、次の地点の経路をdfs()の引数に設定して、dfs()自身を再帰呼び出しします。

サンプルコード

下記がサンプルコードになります。

下記が実行結果になります。

スポンサーリンク