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

グラフ構造・木のメニュー

hogeちゃん

2023.06.07

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

問題【STEP: 1】隣接頂点の出力 2

Task

無向グラフの隣接リストが与えられるので頂点 s の隣接頂点を出力してね。

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

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(...a);  // a の値を出力
         break;
      }
   }
});

hogeちゃんの画像

入力条件が (1 ≦ v_i …) で (1 ≦ a_{i,j} < a_{i,j+1}) なので隣接している頂点をそのまま出力すればOKでした。

問題【STEP: 2】グラフのウォーク 2

Task

無向グラフの頂点 s から k 回移動する経路(反復OK)を全て出力してね。

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

reader.on('close', () => {
   const dfs = (now, route, times) => {  // (現在地, 移動履歴, 移動回数の残)
      if (times === 0) {  // 移動回数の残が 0 なら…
         Walks.push(route.map(e => e + 1));  // Walks に移動履歴を保存
      } else {
         const nexts = list[now];  // 現在地に隣接している頂点
         for (const next of nexts) {  // 現在地に隣接している各頂点(next)について…
            dfs(next, [...route, next], times - 1);  // (next に移動, 移動履歴に next を追加, 移動回数の残 -1)
         }
      }
   };
   const [n, s, k] = lines.shift().split(' ').map(e => e - 0);
   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 Walks = [];  // 経路
   dfs(s - 1, [s - 1], k);
   console.log(Walks.length);
   Walks.forEach(value => {
      console.log(...value);
   });
});

hogeちゃんの画像

処理の流れがよく理解できていない。(´・∀・)?

問題【STEP: 3】グラフのパス 2

Task

無向グラフの頂点 s から k 回移動する経路(反復NG)を全て出力してね。

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

reader.on('close', () => {
   const dfs = (now, route, times) => {  // (現在地, 移動履歴, 移動回数の残)
      if (times === 0) {  // 移動回数の残が 0 なら…
         Walks.push(route.map(e => e + 1));  // Walks に移動履歴を保存
         times = k;
      } else {
         const nexts = list[now];  // 現在地に隣接している頂点
         for (const next of nexts) {  // 現在地に隣接している各頂点(next)について…
            if (!route.includes(next)) {  // route に next が含まれていなければ…
               dfs(next, [...route, next], times - 1);  // (next に移動, 移動履歴に next を追加, 移動回数の残 -1)
            }
         }
      }
   };
   const [n, s, k] = lines.shift().split(' ').map(e => e - 0);
   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 Walks = [];  // 経路
   dfs(s - 1, [s - 1], k);
   console.log(Walks.length);
   Walks.forEach(value => {
      console.log(...value);
   });
});

hogeちゃんの画像

グラフのパスもご参照下さい。

問題【STEP: 4】グラフの s,t パス 2

Task

無向グラフの頂点 s と頂点 t を端点とするパス(反復NG)を全て出力してね。

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

reader.on('close', () => {
   const dfs = (now, route, t) => {  // (現在地, 移動履歴, ゴール)
      if (now === t) {  // 現在地が ゴール なら…
         Walks.push(route.map(e => e + 1));  // Walks に移動履歴を保存
      } else {
         const nexts = list[now];  // 現在地に隣接している頂点
         for (const next of nexts) {  // 現在地に隣接している各頂点(next)について…
            if (!route.includes(next)) {  // route に next が含まれていなければ…
               dfs(next, [...route, next], t);  // (next に移動,移動履歴に next を追加, t)
            }
         }
      }
   };
   const [n, s, t] = lines.shift().split(' ').map(e => e - 0);
   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 Walks = [];  // 経路
   dfs(s - 1, [s - 1], t - 1);
   console.log(Walks.length);
   Walks.forEach(value => {
      console.log(...value);
   });
});

hogeちゃんの画像

グラフの s,t パスもご参照下さい。

問題【STEP: 5】パスの経由地 2

Task

無向グラフの頂点 s と頂点 t を端点とし頂点 p を経由するパス(反復NG)を全て出力してね。

【パスの経由地 2】コード

reader.on('close', () => {
   const dfs = (now, route, t, p) => {  // (現在地, 移動履歴, ゴール, 経由地)
      if (now === t && route.includes(p)) {  // 現在地が ゴール 且つ 移動履歴に p が含まれれば…
         Walks.push(route.map(e => e + 1));  // Walks に移動履歴を保存
      } else {
         const nexts = list[now];  // 現在地に隣接している頂点
         for (const next of nexts) {  // 現在地に隣接している各頂点(next)について…
            if (!route.includes(next)) {  // route に next が含まれていなければ…
               dfs(next, [...route, next], t, p);  // (next に移動, 移動履歴に next を追加, t, p)
            }
         }
      }
   };
   const [n, s, t, p] = lines.shift().split(' ').map(e => e - 0);
   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 Walks = [];  // 経路
   dfs(s - 1, [s - 1], t - 1, p - 1);
   console.log(Walks.length);
   Walks.forEach(value => {
      console.log(...value);
   });
});

hogeちゃんの画像

パスの経由地もご参照下さい。

問題【FINAL】パスの通れない頂点2

Task

無向グラフの頂点 s と頂点 t を端点とし S の頂点を通らないパス(反復NG)を出力してね。

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

reader.on('close', () => {
   const dfs = (now, route, t) => {  // (現在地, 移動履歴, ゴール)
      if (now === t) {  // 現在地が ゴール なら…
         Walks.push(route.map(e => e + 1));  // Walks に移動履歴を保存
      }
      const nexts = list[now];  // 現在地に隣接している頂点
      for (const next of nexts) {  // 現在地に隣接している各頂点(next)について…
         if (!route.includes(next) && !S.includes(next)) {  // 移動履歴が next を含まない 且つ S が next を含まないなら…
            dfs(next, [...route, next], t);  // (next に移動, 移動履歴に next を追加, t)
         }
      }
   };
   const [n, s, t] = lines.shift().split(' ').map(Number);
   const list = new Array(n);
   const k = Number(lines.shift());
   const S = lines.shift().split(' ').map(e => e - 1);
   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 Walks = [];  // 経路
   dfs(s - 1, [s - 1], t - 1);
   console.log(Walks.length);
   Walks.forEach(value => {
      console.log(...value);
   });
});

hogeちゃんの画像

パスの通れない頂点もご参照下さい。

コメント