1 頂点の移動 【幅優先探索・深さ優先探索メニュー 】

幅優先探索・深さ優先探索メニュー【木の深さ優先探索・1 頂点の移動】

問題【STEP: 1】木の深さ優先探索
Task
木の情報と頂点番号 X が与えられるので深さ優先探索をしたときに訪れる頂点番号を順に出力してね。

【木の深さ優先探索】コード 1/2

reader.on('close', () => {
   const bfs = (r, seen, stack) => {
      if (!stack.length) {  // stack が空になったら…
         return;  //  処理終了
      }
      const now = stack.pop();  // stack の末尾の値を取り出し now とする
      const nexts = list[now];  // now と連結している頂点 を nexts に代入
      for (const next of nexts) {  // nexts の各要素について…
         if (!seen[next]) {  // seen[next] が false なら…
            stack.push(next);  // stack に next を追加して…
            seen[next] = true;  // seen[next] を true(訪問済)にする
         }
      }
      console.log(now + 1);  // 頂点番号を出力
      return bfs(now, seen, stack);  // 現在地に移動して再起処理
   };
   const [N, X] = lines.shift().split(' ').map(Number);
   const R = X - 1;
   const list = new Array(N).fill().map(e => []);
   for (let i = 0; i < N - 1; i++) {
   const [a, b] = lines.shift().split(' ').map(e => e - 1);
      list[a].push(b);
      list[b].push(a);
   }
   for (const value of list) {
      value.sort((s, b) => b - s);  // 降順ソート
   }
   const Seen = new Array(N).fill(false);  // 訪問済かどうかの真偽値
   Seen[R] = true;  // スタート地点を訪問済みにする
   bfs(R, Seen, [R]);
});
hogeちゃんの画像

スタック(後入先出法)で深さ優先探索。

top

【木の深さ優先探索】コード 2/2

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, X] = lines.shift().split(' ').map(Number);
   const list = new Array(N).fill().map(e => []);
   for (let i = 0; i < N - 1; 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
問題【FINAL】1 頂点の移動
Task
幅優先探索と深さ優先探索をしたとき注目する未訪問の頂点数が少なくなるのはどちらになる？

【1 頂点の移動】コード 1/2

reader.on('close', () => {
   const bfs = (node, seen, que, count) => {
      if (node === Y - 1) {
         return count;  // 訪問した頂点数を出力
      }
      const now = que.shift();  // que の先頭から要素を取り出し now とする
      const nexts = list[now];  // now と連結している頂点
      for (const next of nexts) {  // now と連結している各頂点が…
         if (!seen.has(next)) {  // 未訪問なら…
            que.push(next);  // qur に next を追加して…
            seen.add(next);  // 訪問済にする
         }
      }
      return bfs(now, seen, que, count + 1);  // 現在地に移動, 移動回数 + 1 で再起処理
   };
   const dfs = (node, seen, stack, count) => {
      if (node === Y - 1) {
         return count;  // 訪問した頂点数を出力
      }
      const now = stack.pop();  // stack の末尾から要素を取り出し now とする
      const nexts = list[now];  // now と連結している頂点
      for (const next of nexts) {  // now と連結している各頂点が…
         if (!seen.has(next)) {  // 未訪問なら…
            stack.push(next);  // stack に next を追加して…
            seen.add(next);  // 訪問済にする
         }
      }
      return dfs(now, seen, stack, count + 1);  // 現在地に移動, 移動回数 + 1 で再起処理
   };
   const [N, X, Y] = lines.shift().split(' ').map(Number);
   const R = X - 1;
   const list = new Array(N).fill().map(e => []);
   for (let i = 0; i < N - 1; i++) {
      const [a, b] = lines.shift().split(' ').map(e => e - 1);
      list[a].push(b);
      list[b].push(a);
   }
   for (const value of list) {
      value.sort((s, b) => s - b);  // 昇順ソート
   }
   const B = bfs(R, new Set([R]), [R], 0);
   for (const value of list) {
      value.sort((s, b) => b - s);  // 降順ソート
   }
   const D = dfs(R, new Set([R]), [R], 0);
   if (D < B) {
      console.log('dfs');
   } else if (D > B) {
      console.log('bfs');
   } else {
      console.log('same');
   }
});
hogeちゃんの画像

キュー(先入先出法)を使えば幅優先探索。

スタック(後入先出法)を使えば深さ優先探索。

top

【1 頂点の移動】コード 2/2

reader.on('close', () => {
   const dfs = (stack, seen, times) => {
      const now = stack.pop();
      if (now === y - 1) {
         return times;
      }
      for (const next of list[now].sort((s, b) => b - s)) {
         if (!seen.includes(next)) {
            stack.push(next);
            seen.push(next);
         }
      }
      return dfs(stack, seen, times + 1);
   };
   const bfs = (queue, seen, times) => {
      const now = queue.shift();  
      if (now === y - 1) {
         return times;
      }
      for (const next of list[now].sort((s, b) => s - b)) {
         if (!seen.includes(next)) {
            queue.push(next);
            seen.push(next);
         }
      }
      return bfs(queue, seen, times + 1);
   };
   const [n, x, y] = lines.shift().split(' ').map(Number);
   const list = new Array(n).fill().map(e => []);
   for (let i = 0; i < n - 1; i++) {
      const [a, b] = lines.shift().split(' ').map(e => e - 1);
      list[a].push(b);
      list[b].push(a);
   }
   const D = dfs([x - 1], [x - 1], 0);
   const B = bfs([x - 1], [x - 1], 0);
   if (D === B) {
      console.log('same');
   } else {
      console.log(D < B ? 'dfs' : 'bfs');
   }
});
hogeちゃんの画像

1/2より少し見やすくなったかな？？

top

コメント