パスの通れない頂点《グラフ・DFS》

グラフ・DFSメニュー【隣接頂点の出力・グラフのウォーク・グラフのパス・グラフの s,t パス・パスの経由地・パスの通れない頂点】

問題【STEP: 1】隣接頂点の出力
Task
隣接リストの 頂点 S に隣接している頂点のうち最も番号の大きいものを出力してね。

【隣接頂点の出力】コード 1

reader.on('close', () => {
   const [n, s] = lines.shift().split(' ').map(Number);
   for (let i = 1; i <= n; i++) {
      const v = Number(lines.shift());  // i に隣接する頂点の数
      const a = lines.shift().split(' ').map(Number);  // i に隣接している頂点
      if (i === s) {  // i が s なら…
         console.log(Math.max(...a));  // a の最大値を出力
         break;
      }
   }
});
hogeちゃんの画像

i が s と一致すれば a の最大値を出力。

top
問題【STEP: 2】グラフのウォーク
Task
完全無向グラフの頂点 S から K 回移動するウォーク(反復可)を 1 つ求めてね。

【グラフのウォーク】コード 1/2

reader.on('close', () => {
   const dfs = (now, route, times) => {  // (現在地, 経路, 移動回数の残)
      if (!times) {  // 移動回数の残が 0 なら…
         return route.map(e => e + 1);  // 経路を返す
      }
      const index = Math.floor(Math.random() * (n - 1));  // list[now]の添字(乱数)
      const next = list[now][index];  // 現在地に隣接している頂点(ランダムに選択)
         return dfs(next,[...route, next], times - 1);  // (next に移動, next を追加した経路, 移動回数の残 -1)
   };
   const [n, s, k] = lines[0].split(' ').map(Number);
   const list = new Array(n).fill().map(e => []);
   for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
         if (j === i) {
            continue;
         }
         list[i].push(j);
      }
   }
   console.log(...dfs(s - 1, [s - 1], k));
});
hogeちゃんの画像

完全無向グラフ…各頂点から他の全ての頂点に枝が存在するグラフ。

top

【グラフのウォーク】コード 2/2

reader.on('close', () => {
   const [n, s, k] = lines[0].split(' ').map(Number);
   const list = new Array(n).fill().map(e => []);  // 隣接リスト
   for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
         if (j === i) {
            continue;
         }
         list[i].push(j);
      }
   }
   const route = [s - 1];
   for (let i = 0; i < k; i++) {  // k 回移動するのでループは k 回
       const index = Math.floor(Math.random() * (n - 1));  // list[route[i]]の添字(乱数)
      route.push(list[route[i]][index]);  // list[route[i]]に隣接している頂点を route に追加
   }
   console.log(...route.map(e => e + 1));
});
hogeちゃんの画像

k 回移動するのでループは k 回。移動先は 乱数を取得して list[route[i] の要素の中からランダムに選択。

top
問題【STEP: 3】グラフのパス
Task
完全無向グラフの頂点 S から K 回移動する経路 (頂点と枝の反復禁止) を求めてね。

【グラフのパス】コード 1/2

reader.on('close', () => {
   const dfs = (now, route, times) => {  // (現在地, 経路, 移動回数の残)
      if (!times) {  // 移動回数の残が 0 なら…
         return route.map(e => e + 1);  // 経路を返す
      }
      const nexts = list[now];  // 現在地に隣接している頂点
      for (const next of nexts) {  // 隣接している頂点が…
         if (!route.includes(next)) {  // 経路に含まれていなければ…
            return dfs(next, [...route, next], times - 1);  // (nextに移動, next を追加した経路, 移動回数の残 -1)
         }
      }
   };
   const [n, s, k] = lines[0].split(' ').map(Number);
   const list = new Array(n).fill().map(e => []);
   for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
         if (j === i) {
            continue;
         }
         list[i].push(j);
      }
   }
   console.log(...dfs(s - 1, [s - 1], k));
});
hogeちゃんの画像

「頂点と枝の反復禁止」なので next が route に含まれていなければ next に移動して再起処理。

top

【グラフのパス】コード 2/2

reader.on('close', () => {
   const [n, s, k] = lines[0].split(' ').map(Number);
   const list = new Array(n).fill().map(e => []);  // 隣接リスト
   for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
         if (j === i) {
            continue;
         }
         list[i].push(j);
      }
   }
   const route = [s - 1];
   for (let i = 0; i < k; i++) {
      let index = 0;  // list[route[i]]の添字
      while (route.includes(list[route[i]][index])) {  // route が list[route[i]][index] を含む間…
         index++;  // 添字の値を + 1
      }
      route.push(list[route[i]][index]);  // 未訪問の頂点を route に追加
   }
   console.log(...route.map(e => e + 1));
});
hogeちゃんの画像

未訪問の頂点が見つかるまで index の値を ++。

top
問題【STEP: 4】グラフの s,t パス
Task
頂点 s と t を端点とするパスのうち最も頂点数の少ないものを求めてね。

【グラフの s,t パス】コード

reader.on('close', () => {
   const dfs = (now, route) => {
      const nexts = list[now];  // nexts は now の隣接頂点
      for (const next of nexts) {  // nexts の各要素 next に対して…
         const l = route.length;  // l に route の要素数を代入
         if (!route.includes(next) && l < L) {  // next が未訪問ならば…
            switch (next === t - 1) {
            case true:  // next がゴール地点なら…
               L = l;
               min_path = [...route, next];  // route に next を追加して min_path を上書き
               break;
            case false:  // ゴールに未到達なら…
               dfs(next,[...route, next]);  // (nextに移動, next を追加した経路)
               break;
            }
         }
      }
   };
   const [n, s, t] = lines.shift().split(' ').map(Number);
   const list = new Array(n).fill().map(e => []);
   for (let i = 0; i < n; i++) {
      const v = Number(lines.shift());
      const a = lines.shift().split(' ').map(e => e - 1);
      list[i] = a;
   }
   let L = n;
   let min_path = [];
   dfs(s - 1, [s - 1]);
   console.log(...min_path.map(e => e + 1));
});
hogeちゃんの画像

再帰関数について いろいろ調べました。
いつもお気楽に実行しているconsole.log() って副作用…？？

top
問題【STEP: 5】パスの経由地
Task
頂点 p を経由する頂点 s と t を端点とするパスのうち最も頂点数の少ないものを求めてね。

【パスの経由地】コード

reader.on('close', () => {
   const dfs = (now, route) => {
      const nexts = list[now];
      const l = route.length;
      if (l < L) {
         for (const next of nexts) {  // now の全ての隣接頂点 next に対して
            if (!route.includes(next)) {  // next が未訪問で…
               switch (next === t - 1 && route.includes(p - 1)) {
               case true:  // next がゴール地点 且つ route.に p - 1 が含まれる場合…
                  L = l;
                  min_path = [...route, next];  // route に next を追加して min_path を上書き
                  break;
               case false:  // 条件に該当しない場合…
                  dfs(next, [...route, next]);  // route に next を追加して再起処理
                  break;
               } 
            }
         }
      }
   };
   const [n, s, t, p] = lines.shift().split(' ').map(Number);
   const list = new Array(n).fill().map(e => []);
   for (let i = 0; i < n; i++) {
      const v = Number(lines.shift());
      const a = lines.shift().split(' ').map(e => e - 1);
      list[i] = a;
   }
   let L = n;
   let min_path = [];
   dfs(s - 1, [s - 1]);
   if (min_path.length) {
      console.log(...min_path.map(e => e + 1));
   } else {
      console.log(-1);
   }
});
hogeちゃんの画像

STEP: 4 は next  がゴール地点なら… route に next を追加して min_path を上書きでしたが STEP: 5 は 条件が増えて next  がゴール地点 且つ  route に p – 1 が含まれる場合…になりました。

top
問題【FINAL】パスの通れない頂点
Task
S に含まれる頂点を通らない s と t を端点とする最も頂点数の少ないパスを求めてね。

【パスの通れない頂点】コード

reader.on('close', () => {
   const dfs = (now, route) => {
      const nexts = list[now];
      const l = route.length;
      if (l < L) {
         for (const next of nexts) {  // now の隣接頂点 next に対して…
            if (!route.includes(next) && !S.includes(next)) {  // next が未訪問で…
               switch (next === t - 1) {
               case true:  // next がゴール地点なら…
                  L = l;
                  min_path = [...route, next];  // route に next を追加して min_path を上書き
                  break;
               case false:  // 条件に該当しない場合…
                  dfs(next, [...route, next]);  // route に next を追加して再起処理
                  break;
               } 
            }
         }
      }
   };
   const [n, s, t] = lines.shift().split(' ').map(Number);
   const k = Number(lines.shift());
   const S = lines.shift().split(' ').map(e => e - 1);
   const list = new Array(n).fill().map(e => []);
   for (let i = 0; i < n; i++) {
      const v = Number(lines.shift());
      const a = lines.shift().split(' ').map(e => e - 1);
      list[i] = a;
   }
   let L = n;
   let min_path = [];
   dfs(s - 1, [s - 1]);
   if (min_path.length) {
      console.log(...min_path.map(e => e + 1));
   } else {
      console.log(-1);
   }
});
hogeちゃんの画像

s の要素数がわからないのでforEach で s に含まれる 要素を List から削除しました。

コメント