タグアーカイブ: 幅優先探索

木構造の探索・深さ優先探索・幅優先探索

深さ優先探索(前順) 以前紹介した2分木の表示では、再帰呼び出しで木の処理を記述していた。しかし、スタックを使って未処理のノードを保存しながらノードに対する処理を行えば、ループ処理で「すべての木のノード」に対する処理を […]

配列やリスト構造のデータの中から、目的となるデータを探す場合、配列であれば2分探索法が用いられる。これにより、配列の中からデータを探す処理は、O(log N)となる。(ただし事前にデータが昇順に並んでいる必要あり) // […]

2分探索木の説明で、深さ優先探索、幅優先探索の話をしたので、補足説明。幅優先探索(breadth-first search)は、待ち行列を使って実装可能なことを示すサンプルコード。待ち行列は授業で説明したFIFOでは、 […]