[Python] 幅優先探索アルゴリズム

グラフのアルゴリズムが出てきて、初見だったので備忘録として書いています。

そもそもグラフって、どうやってプログラム書くんやって、情弱の僕は知りませんでした。。。

この記事で扱うのは、幅優先探索 というグラフ探索アルゴリズムです。

幅優先探索とは

グラフに対する探索アルゴリズム

以下の2つの質問に答えるのに役に立つ。

  1. AからBへの経路は存在するのか??
  2. AからBへの最短経路は何か??

まあ、2点間の最短距離を見つけ出すことができる。と思ってもらえればいいです。

実用例

様々なところで活用されているらしいです。

  • 最小手数で勝つための駒の動き
  • もっとも近い間柄の人を探す
  • などなど。。。

 

なるほど、最短距離で何か対象を見つけたいときに使われるんですね。

コード例

実際に、pythonでコード書いてみました。

コード下の図と一緒にコードをおってもらえれば理解しやすいかと思います。

 

 

グラフを、dictで表現するところが肝ですね。

まとめ

アルゴリズムを勉強していると、様々なサービスの実装側が見えてきて楽しいです。

もっと勉強しないと!

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA