幅優先

Tweet

幅優先ってなに？

幅優先探索は解を探すために、グラフの全てのノードを網羅的に展開・検査する。最良優先探索とは異なり、グラフ全体を目的のノードがみつかるまで、目的のノードに接近しているかどうかなどは考慮せず探索する(Wikipedea)。

実装_キュー

幅優先の探索は、「キュー」と呼ばれるデータ構造を用いて実装できる。
ここでは、キューを使って実装する。

コード

import os
import queue

# ベースとなるパスとパスを入れておくリスト
basePath = os.path.join(os.path.join(os.environ['USERPROFILE']), 'Sample')
baseDir = os.listdir(path=basePath)
#検索対象のファイル
target = "ロース"
#キュー(キューにはpathを保存する)
que = queue.Queue()

# 最初に取得できるフォルダをスタックに保存する
for i in baseDir:
    path = basePath + '\\' + i
    que.put(path)

print('検索対象のファイル名：', target)


# フォルダ取得
def searchDir(path):
    try:
        # 子があるとき
        # 取得したフォルダ(複数)を
        matchDirs = os.listdir(path=path)
        for i in matchDirs:
            # キューにpathを入れる
            newPath = path + '\\' + i
            que.put(newPath)
    except:
        # 子がないとき
        return None


while not que.empty():
    targetPath = que.get()
    print('検索対象：', targetPath)

    if (targetPath.count(target) == 0):
        searchDir(targetPath)
    else:
        print("見つかりました")
        print("答え：", targetPath)
        break

if que.empty():
    print("見つかりませんでした")

出力

見つかるとき

見つからないとき

検索の順路