ottatiのブログ

無職学生がネットにクソアプリをまき散らしていく様子

通勤・通学中に理解する深さ優先探索と幅優先探索【アルゴリズム】

f:id:ottati:20150103125718g:plain     🍣

まえおき

まえおき は みつかりませんでした。

深さ優先探索の例

例から入る

  • 0という名前の点から探索を始める

f:id:ottati:20140131082725p:plain

  • 0につながってるのは1か2か3だけど、テキトーに3を選ぶ

f:id:ottati:20140131082941p:plain

  • 3につながってるのは0か4か5だけど、0は訪問済みなので選択肢は4か5
  • テキトーに4を選ぶ

f:id:ottati:20140131082743p:plain

  • 4につながってるのはは2か6だけど(3は訪問済み)、テキトーに2を選ぶ

f:id:ottati:20140131083047p:plain

  • 2につながってるのは0と4だけど、どっちも訪問済み
  • 直前に来た4に戻って行けるとこを探す
  • 4につながってるのは2と3と6だけどまだ行ってない6を選ぶ

f:id:ottati:20140131082809p:plain

  • 6から行けるとこはどこもない(4は訪問済み)
  • 戻って4から行けるところを探すけどどこも訪問済み
  • 更に戻って3から行けるところを探す
  • 5を選ぶ(0と4は訪問済み)

f:id:ottati:20140131082820p:plain

  • 5から行けるとこはどこもない(3は訪問済み)
  • 戻って3から行けるところを探すけど、どこも訪問済み
  • 更に戻って0から行けるところを探す
  • 1を選ぶ(2と3は訪問済み)

f:id:ottati:20140131082836p:plain

  • 1から行けるとこはない
  • 0に戻る
  • 0からいけるとこもない
  • 戻るとこもない
  • 終わり

探索終了。0から始まる隣接した全ての点を晒しあげることができた。

幅優先探索の例

キューという言葉があるけど知らなくても読めるようにしました。多分。

  • 0をスタート地点とする
  • 空のキューを用意する
  • キュー: {}

f:id:ottati:20140131085626p:plain

  • 0につながってるのは3と1なのでそれらを探索済みとする
  • キューのケツへ探索済みとマークした順につっこむ(今回はテキトーに3, 1の順にマークしたとする)
  • キュー: {3, 1}

f:id:ottati:20140131085650p:plain

  • キューの先頭、つまり3を取り出す
  • キュー: {1}
  • 3につながっているのは0, 4, 5であるが0はマーク済みなので4と5を新たに探索済みとする
  • キューのケツへマークした順につっこむ(今回は4, 5の順にマークしたとする)
  • キュー: {1, 4, 5}

f:id:ottati:20140131085704p:plain

  • キューの先頭、つまり1を取り出す
  • キュー: {4, 5}
  • 1につながっているのは0, 2, 4であるが0, 4はマーク済みなので2を探索済みとする
  • キューのケツへマークした順につっこむ(今回は2だけしかない)
  • キュー: {4, 5, 2}

f:id:ottati:20140131085717p:plain

  • キューの先頭、つまり4を取り出す
  • キュー: {5, 2}
  • 4につながっているのは1, 3であるがどちらもマーク済みなので4から新たにマークするところはない
  • キューの先頭、つまり5を取り出す
  • キュー: {2}
  • 6を探索済みとする(3はマーク済み)
  • キューのケツへ6をつっこむ
  • キュー: {2, 6}

f:id:ottati:20140131085725p:plain

  • キューの先頭、つまり2を取り出す
  • キュー: {6}
  • 2につながっているのは1であるがマーク済みなので2から新たにマークするところはない
  • キューの先頭、つまり6を取り出す
  • キュー: {}
  • 6につながっているのは5であるがマーク済みなので6から新たにマークするところはない
  • キューの先頭…、キューが空になっちまった!
  • 終わり

探索終了。0から始まる隣接した全ての点を晒しあげることができた。

深さ優先探索幅優先探索の違い

f:id:ottati:20140131092032p:plain

最近ペンタブを買ったので絵を書きやすくなった。