4.3木構造での探索

  • check幅優先探索、深さ優先探索を理解する。
  • check行きがけ順、通りがけ順、帰りがけ順の違いを理解する。
  • check再帰的な関数を実装できるようになる。

face階層構造のデータからの探索を考える

リストに格納されている単純なデータを探索する場面だけでなく、階層構造になっているデータを探索する場面もあります。

たとえば、コンピュータのフォルダ内に保存されているファイルを探してみます。ファイル名が「sample.txt」という名前のファイルを一覧にすることを考えると、その探索方法は大きく分けて2通りが考えられます。

それは、「幅優先探索」と「深さ優先探索」です(図4.5)。

幅優先探索

探索を開始するところから近いものをリストアップし、さらにそれぞれを細かく調べていく方法を幅優先探索といいます。本を読むときに目次を見て全体を把握し、さらにそれぞれの章について概要を読み、さらに内容を読む、というように徐々に深く読んでいくようなイメージです。求める条件に合致するものを1つだけ得られればよく、見つかった時点で処理を終了できる場合には高速に処理できます。 ...

Get Pythonではじめるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量 now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.