幅優先探索



深さ優先探索と同様に、ノードは『訪問済み』『訪問中』『未訪問』の3群に振り分けられる。『訪問中』のノードの中から1つを取り出して、『訪問済み』とする手続きを繰り返す点も深さ優先探索と同じである。違いは次の通り。深さ優先探索では、もっとも新しく『訪問中』ノードとして登録されたノードを『訪問済み』に格上げするのに対し、幅優先探索では、もっとも古く『訪問中』ノードとして登録されたノードを『訪問済み』に格上げする