■ 行きがけ・帰りがけ

行きがけ

• （何に使う？）
• 多重ループの終了条件？
• 有向グラフの閉路判定

帰りがけ

• 木DP
• 全方位木DPの第一段階
• トポロジカルソート（帰りがけの逆順）
  • トポロジカルソートはグラフが連結してなくても考慮する必要がある
  • DFS 帰りがけは指定の1点から始めたときの探索順番。グラフが連結でなくて、指定の1点から到達できない点は帰りがけには含まれない

■ 非再帰DFS

• 木以外のグラフで非再帰DFSするのは微妙かもしれない
  • 非再帰DFSのコードの例

■ 再帰DFS

caller で状態を管理 / callee で状態を管理

とりあえず caller で状態を管理することにする。

• caller で状態を管理

  // seq が現在の状態、seq_list が結果の蓄積物
  fn exec_rec(&self, seq: &mut Vec<usize>, seq_list: &mut Vec<Vec<usize>>) {
      if seq.len() == self.r {
          seq_list.push(seq.clone());
          return;
      }
  
      for i in 0..self.n {
          seq.push(i); // caller で状態(seq)を管理する
          self.exec_rec(seq, seq_list);
          seq.pop();
      }
  }
  

  初回呼び出し時にも caller 呼び出し規則（状態管理）を守る必要があるのが注意点

• callee で状態を管理

  // seq が現在の状態、seq_list が結果の蓄積物
  fn exec_rec(&self, seq: &mut Vec<usize>, seq_list: &mut Vec<Vec<usize>>) {
      seq.push(i); // callee で状態(seq)を管理する
  
      if seq.len() == self.r {
          seq_list.push(seq.clone());
          return;
      }
  
      for i in 0..self.n {
          self.exec_rec(seq, seq_list);
      }
      seq.pop();
  }
  

  callee 管理の処理が上と下に分かれてしまうのがデメリット。

■ 葉で評価するタイプの DFS