トレイルの通れない頂点《グラフ・DFS》

グラフ・DFSメニュー【グラフのトレイル・〃s,t トレイル・〃最長 s,t トレイル・トレイルの経由地・〃通れない頂点】

問題【STEP: 1】グラフのトレイル
Task
完全無向グラフの頂点 s から k 回移動するトレイル(反復…枝NG・頂点OK)を出力してね。

【グラフのトレイル】コード 1/2

reader.on('close', () => {
    // const lines = ['5 1 5'];
   const dfs = (now, route, times) => {  // (現在地, 移動履歴, 移動回数の残)
      if (times === 0) {  // 移動回数の残が 0 なら…
         return route.map(e => e + 1);  // 移動履歴を返す
      } else {
         const nexts = list[now];  // 現在地に隣接している頂点
         let next = nexts[0];  // 次の移動候補地
         while (passed[now].includes(next)) {  // 移動候補地へのルートが通過済の間…
            const index = Math.floor(Math.random() * nexts.length);  // 乱数(0 ~ nexts の要素数 - 1)
            next = nexts[index];  // 次の移動候補地を更新
         }
         passed[now].push(next);
         passed[next].push(now);
         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 => []);
   const passed = 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ちゃんの画像

トレイル…枝の反復を許さず頂点の反復を許す経路。

移動先の数字入りの隣接行列? を生成してから ランダムに行き先を選び 行き先が 0 じゃなければ移動して 枝を削除しています。

top

【グラフのトレイル】コード 2/2

reader.on('close', () => {
   const dfs = (now, route, times) => {  // (現在地, 移動履歴, 移動回数の残)
      if (times === 0) {  // 移動回数の残が 0 なら…
         return route.map(e => e + 1);  // 移動履歴を返す
      } else {
         const nexts = [...node];  // 移動候補
         nexts.splice(now, 1);  // 移動候補から now と同じ値を削除
         let index = 0;
         let next = nexts[index];  // 移動候補
         while (passed[now].includes(next)) {  // 移動候補への枝が通過済みなら…
            index++;  // index を増やして…
            next = nexts[index];  // 次を探索
         }
         passed[now].push(next);  // next への枝が通過済みにする
         passed[next].push(now);
         return dfs(next, [...route, next], times - 1);  // (next に移動, 移動履歴に next を追加, 移動回数の残 -1)
      }
   };
   const [n, s, k] = lines[0].split(' ').map(Number);
   const node = [];
   for (let i = 0; i < n; i++) {
      node.push(i);
   }
   const passed = new Array(n).fill().map(e => []);
   console.log(...dfs(s - 1, [s - 1], k));
});
hogeちゃんの画像

完全無向グラフなので 各頂点の隣接頂点は  n – 1 個。

top
問題【STEP: 2】グラフの s,t トレイル
Task
無向グラフの頂点 s,t を端点とする最も頂点数の多いトレイル(s.t通過NG)を出力してね。

【グラフの s,t トレイル】コード 1/2

reader.on('close', () => {
   const dfs = (now, trail, edges) => {
      const nexts = list[now];
      for (const next of nexts) {
         const [node1, node2] = [Math.max(next, now), Math.min(next, now)];
         if (!edges[node1].includes(node2)) {  // 枝 (node1↔node2) が通過済みでないならば
            if (next !== s - 1) {
               edges[node1].push(node2);
               if (next === t - 1) {  // next が ゴール地点なら…
                  if (Max_Trail.length <= trail.length) {  // Max_Trail の要素数が trail の要素数以下なら…
                     Max_Trail.length = 0;  // Max_Trail の要素を削除して…
                     Max_Trail.push(...trail, next);  // Max_Trail に trail, next を保存
                  }
               } else {  // ゴールに到達していなければ…
                  dfs(next, [...trail, next], edges);  // (next に移動, trail に next を追加, edges)で再起処理
               }
               edges[node1].pop();
            }
         }
      }
   };
   const [n, s, t] = lines.shift().split(' ').map(e => e - 0);
   const list = new Array(n);
   for (let i = 0; i < n; i++) {
      const now = Number(lines.shift());
      const a = lines.shift().split(' ').map(e => e - 1);
      list[i] = a;
   }
   const passed = new Array(n).fill().map(e => []);
   const Max_Trail = [];  // 経路
   dfs(s - 1, [s - 1], passed);
   console.log(...Max_Trail.map(e => e + 1));
});
hogeちゃんの画像

枝は反復不可で 頂点はスタート地点とゴール地点以外は反復OK。通過済みの枝は2次元配列に記録しました。

top

【グラフの s,t トレイル】コード 2/2

reader.on('close', () => {
   const dfs = (now, trail, edges) => {
      list[now].forEach(next => {
         const edge = Math.max(next, now) * 10 + Math.min(next, now);
         if (!edges.includes(edge)) {  // 枝 (now,next) が通過済みでないならば
            trail.push(next);
            if (next !== s - 1 && next === t - 1) {
               // edges.push(edge);
               if (Max_Trail.length < trail.length) {
                  Max_Trail = [...trail];
               }
            } else if (next !== s - 1) {
               dfs(next, trail, [...edges, edge]);
               // edges.pop(); }
            trail.pop();
         }
      });
   };
   const [n, s, t] = lines.shift().split(' ').map(Number);
   const list = new Array(n);
   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 Max_Trail = [];  // 経路
   dfs(s - 1, [s - 1], []);
   console.log(...Max_Trail.map(e => e + 1));
});
hogeちゃんの画像

dfs() の edge (通過済みの枝)の値は( next と now の大きい方✕10) + next と now の小さい方) で一つの数値に変換しました。

top
問題【STEP: 3】グラフの最長 s,t トレイル
Task
無向グラフの頂点 s,t を端点とする最も頂点数の多いトレイル(s.t通過OK)を出力してね。

【グラフの最長 s,t トレイル】コード

reader.on('close', () => {
   const dfs = (now, trail, edges) => {
      const nexts = list[now];
      for (const next of nexts) {
         const [node1, node2] = [Math.max(next, now), Math.min(next, now)];
         if (!edges[node1].includes(node2)) {  // 枝 (node1↔node2) が通過済みでないならば
            edges[node1].push(node2);
            if (next === t - 1) {
               if (Max_Trail.length <= trail.length) {
                  Max_Trail.length = 0;
                  Max_Trail.push(...trail, next);
               }
            }
            dfs(next, [...trail, next], edges);
            edges[node1].pop();
         }
      }
   };
   const [n, s, t] = lines.shift().split(' ').map(e => e - 0);
   const list = new Array(n);
   for (let i = 0; i < n; i++) {
      const S = Number(lines.shift());
      const a = lines.shift().split(' ').map(e => e - 1);
      list[i] = a;
   }
   const passed = new Array(n).fill().map(e => []);
   const Max_Trail = []; // 経路
   dfs(s - 1, [s - 1], passed);
   console.log(...Max_Trail.map(e => e + 1));
});
hogeちゃんの画像

【STEP: 2】コード 2/2 と ほぼ同じ。s.t通過OKなので if (next !== s – 1) {}と dfs(next, […trail, next], edges)を呼び出す前の  else の部分を削除したらOKでした。

top
問題【STEP: 4】トレイルの経由地
Task
完全無向グラフの頂点 s と t を端点とし p の通過数が最多のトレイルを出力してね。

【トレイルの経由地】コード

reader.on('close', () => {
   const dfs = (now, trail, edges) => {
      list[now].forEach(next => {
         const edge = Math.max(next, now) * 10 + Math.min(next, now);
         if (!edges.includes(edge)) {  // 枝 (now,next) が通過済みでないならば
            trail.push(next);
            edges.push(edge);
            if (next === t - 1) {
               let p_num = 0;
               trail.forEach(t => {
                  if (t === p - 1) {
                     p_num++;
                  }
               });
               if (p_num > P_num) {
                  Max_Trail = [...trail.map(e => e + 1)];
                  P_num = p_num;
               }
            }
            dfs(next, trail, edges);
            edges.pop();
            trail.pop();
         }
      });
   };
   const [n, s, t, p] = lines.shift().split(' ').map(Number);
   const list = new Array(n);
   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 P_num = 0;
   let Max_Trail = [];  // 経路
   dfs(s - 1, [s - 1], []);
   console.log(P_num ? Max_Trail.join(' ') : -1);
});
hogeちゃんの画像
p の通過回数を 変数に保存して p_num > P_num なら Max_Trail を更新しています。
top
問題【FINAL】トレイルの通れない頂点
Task
無向グラフの頂点 s と t を端点とし S の頂点を通らないトレイルを出力してね。

【トレイルの通れない頂点】コード

reader.on('close', () => {
   const dfs = (now, trail, edges) => {
      list[now].forEach(next => {
         const edge = Math.max(next, now) * 10 + Math.min(next, now);
         if (!edges.includes(edge) && !S.includes(next)) {  // 枝 (now,next) が通過済みでないならば
            trail.push(next);
            edges.push(edge);
            if (next === t - 1) {
               if (Max_Trail.length < trail.length) {
                  Max_Trail = [...trail];
               }
            }
            dfs(next, trail, edges);
            trail.pop();
            edges.pop();
         }
      });
   };
   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);
   for (let i = 0; i < n; i++) {
      const now = Number(lines.shift());
      const a = lines.shift().split(' ').map(e => e - 1);
      list[i] = a;
   }
   let Max_Trail = [];  // 経路
   dfs(s - 1, [s - 1], []);
   console.log(Max_Trail.length ? Max_Trail.map(e => e + 1).join(' ') : -1);
});
hogeちゃんの画像

頂点の集合 S に含まれる頂点は通れないので 事前に DFS() を呼び出す前に グラフから頂点を削除しました。

top

コメント