組合せとグラフの理論(塩田)2022年度 第6回

 木とは、頂点を与えたときに、もっとも少ない辺数でそれらを連結にできるグラフであり、 基本的なデータ構造のひとつです。 今日は木の定義と基本的性質を学び、次いで、グラフの中の木を探す基本的なアルゴリズムとして、 幅優先探索、深さ優先探索の2つを学びます。

  1. 全域木
  2. 幅優先探索
  3. 深さ優先探索
  4. 幅優先探索・深さ優先探索の応用
  5. デモ動画、今日のまとめと宿題