2 頂点間の距離【幅優先探索・深さ優先探索メニュー 】

幅優先探索・深さ優先探索メニュー【グラフでの幅優先探索 ・2 頂点間の距離 】

  1. グラフでの幅優先探索
  2. 2 頂点間の距離
問題【STEP: 1】グラフでの幅優先探索
Task
無向グラフの頂点 X から幅優先探索をおこなったとき 訪問する頂点を順に出力してね。

【グラフでの幅優先探索】コード 1/2

reader.on('close', () => {
   const bfs = (current, nexts, seen) => {
      if (!current.length) {
         return seen;
      }
      for (const now of current) {
         for (const next of list[now]) {  // 次の階層の各値
            if (!seen.has(next)) {  // 未訪問なら
               nexts.add(next);  // 次の移動候補地
               seen.add(next);  // 訪問済
            }
         }
      }
      return bfs([...nexts], new Set(), seen);  // current を nexts に置換して再起処理
   };
   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);
   }
   for (let i = 0; i < N; i++) {
      list[i] = list[i].sort((s, b) => s - b);  // 昇順に並べ替え
   }
   const route = bfs([X - 1], new Set(), new Set([X - 1]));
   route.forEach(r => {
      console.log(r + 1);
   });
});
hogeちゃんの画像

seen (訪問済みの頂点を保存するセット)が戻り値。

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

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

reader.on('close', () => {
   const bfs = (current, nexts, seen, level) => {
      if (current.includes(Y)) {
         return level;
      }
      if (!current.length) {
         return -1;
      }
      for (const now of current) {
         for (const next of list[now]) {  // 次の階層の各値
            if (!seen.has(next)) {  // 未訪問なら
               nexts.push(next);
               seen.add(next);  // 訪問済
            }
         }
      }
      return bfs(nexts, [], seen, level + 1);  // current を nexts に置換, level + 1  で再起処理
   };
   const [N, M, x, y] = 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 [X, Y] = [x, y].map(e => e - 1);
   console.log(bfs([X], [], new Set([X]), 0));
});
hogeちゃんの画像

level + 1 で再起処理して Y に到達すれば level を戻り値にして処理終了。

top

コメント