アルゴリズムのお勉強（２）- 深さ優先探索(DFS)

f:id:robonchu:20190520021125p:plain — Wikipedia - 深さ優先探索

やりたいこと

深さ優先探索について学ぶ

深さ優先探索とは

上図のように繋がっているノードを上から下へ順々に探索。再帰関数かスタックで解ける。

詳細は以下参照。

Wiki先生。pythonでの実装例ある。さすが。
- 深さ優先探索 - Wikipedia
イラスト付きで説明されているもの。
- 知れば天国、知らねば地獄――「探索」虎の巻 - ITmedia エンタープライズ
コーディングのイメージがつかめる説明。
- 深さ優先探索を実装してみる。 - Qiita
  - 再帰関数を用いる
  - スタックを用いる

深さ優先探索を用いて解く例題

atcoder.jp
- AtCoder Beginner Contest 126のD問題より抜粋

問題: D - Even Relation

f:id:robonchu:20190520021705p:plain

入力

f:id:robonchu:20190520021747p:plain

出力

f:id:robonchu:20190520022010p:plain

制約

f:id:robonchu:20190520021905p:plain

入力/出力例

入力

3
1 2 2
2 3 1

出力

0
0
1

深さ優先探索を用いた実装例(C++)

再帰関数を用いた実装

#include <iostream>
#include <vector>
 
using namespace std;
const int MAX_N = 100001;

// 対象のノード番号の要素にそれに隣接するノード名とその距離のペアが入る
vector<std::pair<int, int>> vm[MAX_N];
int ans[MAX_N];

// 第1引数に対象ノード番号を入れる
// 第2引数はすでにチェックした番号を示す
void DFS(int target, int checked){
  for(int i=0; i < vm[target].size(); ++i){
    int nn = vm[target][i].first;  // 隣接ノード番号を格納
    if(nn == checked) continue;  //チェックしたものの場合は飛ばす
    
    if(vm[target][i].second % 2) {
      // 2で割り切れない場合、白黒を入れ替える
      if(ans[target]) ans[nn] = 0;
      else ans[nn] = 1;
    }else{
      ans[nn] = ans[target];
    }
    DFS(nn, target);
  }
}

 
int main(){
  int n;
  cin >> n;

  int u, v, w;
  for(int i=0; i<n-1; ++i){
    cin >> u >> v >> w;
    // u,vの同じノード番号の要素に値を追加。
    vm[u].push_back(std::make_pair(v,w));
    vm[v].push_back(std::make_pair(u,w));
  }
 
  // 1から順に探索を始める。1は最初に探索するので、第2引数にもセット。
  DFS(1, 1);

  for(int i=1; i<=n; ++i){
    cout << ans[i] << endl;
  }
  return 0;
}