ホーム » スタッフ » 斉藤徹 » 講義録 » オブジェクト指向 » 深さ優先探索と幅優先探索

2021年10月
 12
3456789
10111213141516
17181920212223
24252627282930
31  

検索・リンク

深さ優先探索と幅優先探索

2分探索木の説明で、深さ優先探索、幅優先探索の話をしたので、補足説明。

幅優先探索(breadth-first search)は、待ち行列を使って実装可能なことを示すサンプルコード。待ち行列は授業で説明したFIFOでは、データ件数0になる際の処理を手抜きで説明しているため、C++ の deque で記述。

深さ優先探索(deep-first search)は、スタックを使って実装可能なことを示すために、あえて再帰呼び出しを使わずに記述してみた。

#include <deque>
#include <algorithm>

int main() {
   std::deque<struct Tree*> deq ;
   struct Tree* p ;
   // 幅優先探索(FIFOを使って)
   deq.push_front( top ) ;
   while( !deq.empty() ) {
      // 待ち行列の最初を取り出す
      p = deq.front() ;
      deq.pop_front() ;
      if ( p != NULL ) {
         printf( "%d\n" , p->data ) ;
         // 待ち行列に枝葉を追加
         deq.push_back( p->left ) ;
         deq.push_back( p->right ) ;
      }
   }
   // 深さ優先探索(再帰呼び出しを使わずstack/LIFOで実装)
   p = top ;
   for( ;; ) {
      // 分岐をpushしながら左下にまっしぐら
      while( p != NULL ) {
         deq.push_front( p ) ;
         p = p->left ;
      }
      if ( deq.empty() )
         break ;
      // pushしておいた分岐点をpopして繰り返し
      p = deq.front() ;
      deq.pop_front() ;
      printf( "%d\n" , p->data ) ;
      p = p->right ;
   }
   return 0 ;
}