連結成分の個数 【幅優先探索・深さ優先探索メニュー 】

幅優先探索・深さ優先探索メニュー【グラフの深さ優先探索・二部グラフ判定・連結成分の個数】

問題【STEP: 1】グラフの深さ優先探索
Task
無向グラフの 頂点 X から深さ優先探索をしたときに訪れる頂点番号を順に出力してね。

【グラフの深さ優先探索】コード

reader.on('close', () => {
   const dfs = (now, seen) => {
      seen.push(now);  // seen[now]を true(訪問済)にする
      console.log(now + 1);  // 現在の頂点出力
      const nexts = list[now].sort((s, b) => s - b);  // now と連結している頂点
      for (const next of nexts) {  // now と連結している各頂点が…
         if (!seen.includes(next)) {  // 未訪問なら…
            dfs(next, seen);  // next に移動して再起処理
         }
      }
   };
   const [N, M, X] = lines.shift().split(' ').map(Number);
   const list = new Array(N).fill().map(e => []);
   for (let i = 0; i < M; i++) {
   const [a, b] = lines.shift().split(' ').map(e => e - 1);
      list[a].push(b);
      list[b].push(a);
   }
   dfs(X - 1, []);
});
hogeちゃんの画像

now に連結している未訪問の頂点を見つけたら 即移動して探索。解答コード例参照しました。

top
問題【STEP: 2】二部グラフ判定
Task
無向グラフの情報が与えられるので グラフが二部グラフかを判定してね。

【STEP: 2】二部グラフ判定

reader.on('close', () => {
   const dfs = (now, color) => {
      nodes[now] = color;  // 現在の頂点を着色
      const nexts = list[now];  // nexts は現在の頂点に隣接している頂点
      nexts.forEach(next => {  // next (nexts の各要素) について…
         if (nodes[next] === 0) {  // nodes の next 番目が 0 (未着色) なら…
            dfs(next, color*-1);  // (next に移動, color の符号を反転)して再起処理
         }
         if (nodes[now] === nodes[next]) {  // nodes[now] と nodes[next] が同じなら…
            bipart = false;  // 二部グラフに該当しない
            return;
         }
      });
   };
   const [N, M] = lines.shift().split(' ').map(Number);
   const list = new Array(N).fill().map(e => []);
   for (let i = 0; i < M; i++) {
      const [a, b] = lines.shift().split(' ').map(e => e - 1);
      list[a].push(b);
      list[b].push(a);
   }
   let bipart = true;  // 二部グラフであるかどうかの真偽値
   const nodes = new Array(N).fill(0);
   for (let i = 0; i < N; i++) {
      if (nodes[i] === 0 && bipart) {  // nodes[i] が 0 (未着色) 且つ bipart が true なら…
         dfs(i, 1);  // dfs()を呼び出し
      }
   }
   console.log(bipart ? 'Yes' : 'No');
});
hogeちゃんの画像

解答コード例参照しました。

top
問題【FINAL】連結成分の個数
Task
無向グラフの情報が与えられるので 連結成分の個数を求めてね。

【連結成分の個数】コード

reader.on('close', () => {
   const dfs = (now) => {
      seen[now] = true;  // 現在地を訪問済にする
      for (const next of list[now]) {  // next は現在の頂点に隣接している各頂点
         if (seen[next]) {  // すでに訪問済なら…
            continue;  // 処理をスキップ
         }
         dfs(next);
      }
      return;
   };
   const [N, M] = lines.shift().split(' ').map(Number);
   const list = new Array(N).fill().map(e => []);
   for (let i = 0; i < M; i++) {
      const [a, b] = lines.shift().split(' ').map(e => e - 1);
      list[a].push(b);
      list[b].push(a);
   }
   const seen = new Array(N).fill(false);
   let ans = 0;  // 答えとなる変数
   for (let node = 0; node < N; node++) {  // 全ての頂点について
      if (seen[node]) {
         continue;
      }
      dfs(node);
      ans++;
   }
   console.log(ans);
});
hogeちゃんの画像

解答コード例の Java の場合 を参照しました。

top

コメント