YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Japanese subtitles

← 03-20 Breadth First without Recursion

Get Embed Code
3 Languages

Showing Revision 1 created 03/11/2014 by Fran Ontanaya.

  1. 次はこれを幅優先探索に変えますが
    自分でやる場合は簡単で

  2. リストから消す要素の順番が
    最後から最初に変わるだけです
  3. では実際に見ていきましょう
  4. まずはdをオープンリストに加えます
  5. リストにあるのはdだけなので
    最初の要素も最後の要素も同じです
  6. リストからdを消して隣接するノードをマークします
  7. この場合はeとcですがここは前と同じです
  8. そしてここからの手順が変わってきます
  9. 今回は最初と最後の要素の順序が任意なので
    実は大して変わらないのですが
  10. ここでリストの最初の要素であるeを消します
  11. 次は前と同様に隣接するノードを
    リストの最後に加えます
  12. これでノードの下に振る番号順が前と変わってきます
  13. 次にリストの最初の要素であるcを消します
    つまりここでは
  14. 1方向に進む代わりに両側に広がっていきます
  15. 最初がdで次がcとeその次がbとfときています
  16. 次にfを消して隣接するgをリストに加えます
  17. 次はまたリストの最初にあるbを消します
  18. 最後にaをリストに加えて
  19. 次はgですが隣接するノードは
    マーク済みなのでaを消します
  20. aと隣接するノードもマーク済みで
    リストも終わりなのでこれで完了です
  21. 今回はdからスタートして最後はaとgに広がっています
  22. この場合のaとgの合計は12ではなく13になりましたが
    この時点では重要ではありません
  23. しかしこれが処理の違いを示しています
  24. ここで重要なのは処理が中から外へ広がることです
  25. すべてのエッジが外に広がっており
  26. パスは最初のノードから外に向かっています
  27. これが最短経路を見つける手立てになります