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

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

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

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

reader.on('close', () => {
   const dfs = (now, trail, edges, times) => {  // (現在地, 移動履歴, 通過済みの枝, 残りの移動回数)
      if (!times) {  // 残りの移動回数が 0 になったら…
         Trails.push([...trail]);  // Trails に移動履歴を記録
      } else {
         const nexts = list[now];  // 現在地に隣接している頂点
         for (const next of nexts) {  // 現在地に隣接している各頂点について…
            const edge = Math.max(next, now) * 10 + Math.min(next, now);  // edge(枝) = [next, now]の最大値 * 10 + next, now]の最小値
            if (!edges.includes(edge)) {  // edge が通過済みでなければ…
               // trail.push(next);
               // edges.push(edge);
               dfs(next, [...trail, next], [...edges, edge], times - 1);  // (nextに移動, trailにnextを追加, edges,edgeを追加, 移動回数の残 - 1)
               // trail.pop();
               // edges.pop();
            }
         }
      }
   };
   const [n, s, k] = 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;
   }
   const Trails = [];  // トレイルの移動経路
   dfs(s - 1, [s - 1], [], k);
   console.log(Trails.length);
   Trails.forEach(trail => {
      console.log(...trail.map(e => e + 1));
   });
});
hogeちゃんの画像

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

再帰関数で深さ優先探索。

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

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

reader.on('close', () => {
   const dfs = (now, trail, edges, exite) => {  // (現在地, 移動履歴, 通過済みの枝, 出口)
      if (now === exite) {  // 出口に到達したら…
         Trails.push([...trail]);  // Trails に移動履歴を記録
      } else {
         const nexts = list[now];  // 現在地に隣接している頂点
         for (const next of nexts) {  // 現在地に隣接している各頂点について…
            const edge = Math.max(next, now) * 10 + Math.min(next, now);  // edge(枝) = [next, now]の最大値 * 10 + next, now]の最小値
            if (!edges.includes(edge) && next !== s - 1) {  // edge が通過済みでない 且つ 頂点がスタート地点でなければ…
               // trail.push(next);
               // edges.push(edge);
               dfs(next, [...trail, next], [...edges, edge], exite);  // (nextに移動, trailにnextを追加, edgesにedgeを追加, exite)
               // trail.pop();
               // edges.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;
   }
   const Trails = [];  // トレイルの移動経路
   dfs(s - 1, [s - 1], [], t - 1);
   console.log(Trails.length);
   Trails.forEach(trail => {
      console.log(...trail.map(e => e + 1));
   });
});
hogeちゃんの画像

s,tトレイル…同じ道を通らずに s から t へ移動する経路。

top
問題【STEP: 3】グラフの s,t トレイル 3
Task
無向グラフの頂点 s,t を端点とするs, t 双方を通過点としても含むトレイルを全て出力してね。

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

reader.on('close', () => {
   const dfs = (now, trail, edges, exite) => {  // (現在地, 移動履歴, 通過済みの枝, 出口)
      if (now === exite &&  // 出口に到達 且つ…
         trail.indexOf(exite) !== trail.lastIndexOf(exite) &&  // 出口を2回以上通過 且つ…
         trail.indexOf(s - 1) !== trail.lastIndexOf(s - 1)) {  // 入口を2回以上通過していれば…
         Trails.push([...trail]);  // Trails に移動履歴を記録
      }
      const nexts = list[now];  // 現在地に隣接している頂点
      for (const next of nexts) {  // 現在地に隣接している各頂点について…
         const edge = Math.max(next, now) * 10 + Math.min(next, now);  // edge(枝) = [next, now]の最大値 * 10 + next, now]の最小値
         if (!edges.includes(edge)) {  // edge が通過済みでなければ…
            // trail.push(next);
            // edges.push(edge);
            dfs(next, [...trail, next], [...edges, edge], exite);  // (nextに移動, trailにnextを追加, edgesにedgeを追加, exite)
            // trail.pop();
            // edges.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;
   }
   const Trails = [];  // トレイルの移動経路
   dfs(s - 1, [s - 1], [], t - 1);
   console.log(Trails.length);
   Trails.forEach(trail => {
      console.log(...trail.map(e => e + 1));
   });
});
hogeちゃんの画像

移動経路に s・tを含まないといけないので trail.indexOf(value) と trail.lastIndexOf(value)) が一致するかどうかで条件分岐しています。

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

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

reader.on('close', () => {
   const dfs = (now, trail, edges, exite) => {  // (現在地, 移動履歴, 通過済みの枝, 出口)
      if (now === exite &&  // 出口に到達 且つ…
          trail.indexOf(p - 1) !== trail.lastIndexOf(p - 1)) {  // p を2回通過していれば…
         Trails.push([...trail]);  // Trails に移動履歴を記録
      }
      const nexts = list[now];  // 現在地に隣接している頂点
      for (const next of nexts) {  // 現在地に隣接している各頂点について…
         const edge = Math.max(next, now) * 10 + Math.min(next, now);  // edge(枝) = [next, now]の最大値 * 10 + next, now]の最小値
         if (!edges.includes(edge)) {  // edge が通過済みでなければ…
            dfs(next, [...trail, next], [...edges, edge], exite);  // (nextに移動, trailにnextを追加, edgesにedgeを追加, exite)

         }
      }
   };
   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;
   }
   const Trails = [];  // トレイルの移動経路
   dfs(s - 1, [s - 1], [], t - 1);
   console.log(Trails.length);
   Trails.forEach(trail => {
      console.log(...trail.map(e => e + 1));
   });
});
hogeちゃんの画像
移動経路に pを2回以上含まないといけないのでindexOf(p-1) と trail.lastIndexOf(p-1)) が一致するかどうかで条件分岐しています。
top
問題【FINAL】トレイルの通れない頂点 2
Task
無向グラフの頂点 s と t を端点とし S の頂点を通らないトレイルを全て出力してね。

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

reader.on('close', () => {
   const dfs = (now, trail, edges, exite) => {  // (現在地, 移動履歴, 通過済みの枝, 出口)
      if (now === exite) {  // 出口に到達したら…
         Trails.push([...trail]);  // Trails に移動履歴を記録
      }
      const nexts = list[now];  // 現在地に隣接している頂点
      for (const next of nexts) {  // 現在地に隣接している各頂点について…
         const edge = Math.max(next, now) * 10 + Math.min(next, now);  // edge(枝) = [next, now]の最大値 * 10 + next, now]の最小値
         if (!edges.includes(edge) && !S.includes(next)) {  // edge が通過済みでない 且つ S が next を含まないなら…
            dfs(next, [...trail, next], [...edges, edge], exite);  // (nextに移動, trailにnextを追加, edgesにedgeを追加, exite)
         }
      }
   };
   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 v = Number(lines.shift());
      const a = lines.shift().split(' ').map(e => e - 1);
      list[i] = a;
   }
   const Trails = [];  // 経路
   dfs(s - 1, [s - 1], [], t - 1);
   console.log(Trails.length);
   Trails.forEach(trail => {
      console.log(...trail.map(e => e + 1));
   });
});
hogeちゃんの画像

edge が通過済みでない 且つ S が next を含まないなら next へ移動。

top

コメント