2 頂点間の最短経路【幅優先探索・深さ優先探索メニュー 】

幅優先探索・深さ優先探索メニュー 【木の (1 頂点の移動・距離 3 の頂点・幅優先探索での探索・ 2 頂点間の(距離・最短経路)】

問題【STEP: 1】木の 1 頂点の移動
Task
木の頂点 X に隣接する頂点の番号を昇順に全て出力してね。

【木の 1 頂点の移動】コード

reader.on('close', () => {
   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);
   }
   for (const value of List[X - 1].sort((s, b) => s - b)) {
  // List[X - 1]の値を昇順に並べ替えて各値を value に代入
      console.log(value + 1);  // value + 1 を出力
   }
});
hogeちゃんの画像

upしました。

top
問題【STEP: 2】木の距離 3 の頂点
Task
木の頂点 X からの距離が 3 である頂点の番号を全て出力してね。

【木の距離 3 の頂点】コード

reader.on('close', () => {
   const bfs = (que, nexts, seen, level) => {
  // que = キュー, nexts = 次に訪問する頂点, seen = 訪問済みの頂点, level = X からの距離
      if (level === 3) {  // level が 3 になれば…
         return que;  // que を返す
      }
      for (const now of que) {  // que の各値を now に代入
          for (const next of List[now]) {  // now に隣接している各値を next に代入
            if (!seen.includes(next)) {  // seen に next が含まれていなければ…
               nexts.push(next);  // nexts に next を保存
               seen.push(next);  // seen に next を保存
            }
         }
      }
      return bfs(nexts, [], seen, level + 1);  // que を nexts に置き換え再起処理
   };
   const [N, X] = lines.shift().split(' ').map(Number);
   const List = [];
   for (let i = 0; i < N; i++) {
      List.push([]);
   }
   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 ans = bfs([X - 1], [], [X - 1], 0).sort((s, b) => s - b);
   for (const now of ans) {
      console.log(now + 1);
   }
});
hogeちゃんの画像

upしました。

top
問題【STEP: 3】木における幅優先探索での探索
Task
木の距離が L である頂点の番号を全て出力してね。

【木における幅優先探索での探索】コード

reader.on('close', () => {
   const bfs = (que, nexts, seen, level) => {
  // que = キュー, nexts = 次に訪問する頂点, seen = 訪問済みの頂点, level = X からの距離
      if (level === L) {  // level が L になれば…
         return que;  // que を返す
      }
      for (const now of que) {  // que の各値を now に代入
         for (const next of List[now]) {  // now に隣接している各値を next に代入
            if (!seen.includes(next)) {  // seen に next が含まれていなければ…
               seen.push(next);  // nexts に next を保存
               nexts.push(next);  // seen に next を保存
            }
         }
      }
      return bfs(nexts, [], seen, level + 1);  // que を nexts に置き換え level + 1 で再起処理
   };
   const [N, X, L] = 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 ans = bfs([X - 1], [], [X - 1], 0).sort((s, b) => s - b);  // ans に bfs() の戻り値を代入
   for (const now of ans) {
      console.log(now + 1);
   }
});
hogeちゃんの画像

upしました。

top
問題【STEP: 4】木の 2 頂点間の距離
Task
木の情報と頂点番号 X, Y が与えられるので頂点 X, Y 間の距離を出力してね。

【木の 2 頂点間の距離】コード

reader.on('close', () => {
   const bfs = (que, nexts, seen, level) => {
// que = キュー, nexts = 次に訪問する頂点, seen = 訪問済みの頂点, level = X からの距離
      if (que.includes(Y - 1)) {  // que に Y - 1 が含まれていれば…
         return level;  // level  を返す
      }
      for (const now of que) {  // que の各値を now に代入
         for (const next of List[now]) {  // now に隣接している各値を next に代入
            if (!seen.includes(next)) {  // seen に next が含まれていなければ…
               nexts.push(next);  // nexts に next を保存
               seen.push(next);  // seen に next を保存
            }
         }
      }
      return bfs(nexts, [], seen, level + 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 ans = bfs([X - 1], [], [X - 1], 0);  // ans に bfs() の戻り値を代入
   console.log(ans);
});
hogeちゃんの画像
upしました。
top
問題【FINAL】2 頂点間の最短経路
Task
木の 頂点 X から 頂点 Y へ最短経路で移動したときに通過する頂点の番号を出力してね。

【2 頂点間の最短経路】コード

reader.on('close', () => {
   const bfs = (que, nexts, seen, prev, y, root) => {
// que = キュー, seen = 訪問済みの頂点, prev = indexの一つ前の頂点, y = ゴール, root = 経路
      if (que.includes(y)) {  // que に y が含まれていれば…
         while (seen.has(y)) {  // y が訪問済みの間…
            root.unshift(y + 1);  // root の先頭に y + 1を保存
            y = prev[y];  // y を y の前に訪れた頂点で上書き
         }
         return root;  // root を返す
      }
      for (const now of que) {  // qur の各値を now に代入
         for (const next of list[now]) {  // now に隣接している各値を next に代入
            if (!seen.has(next)) {  // seen に next が含まれていなければ…
               prev[next] = now;  // next の前の場所を記録
               nexts.push(next);  // nexts に next を保存
               seen.add(next);  // seen に next を保存
            }
         }
      }
      return bfs(nexts, [], seen, prev, y, root);  // que を nexts に置き換え再起処理
   };
   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 Prev = new Array(N).fill(-1);
   const Root = bfs([X - 1], [], new Set([X - 1]), Prev, Y - 1, []);
   Root.forEach(root => {
      console.log(root);
   });
});
hogeちゃんの画像

upしました。

top

コメント