オイラー閉路の出力《グラフ・DFS》

グラフ・DFSメニュー【閉路の出力・グラフの閉路の総数・通れない頂点が存在する(閉路・閉路の総数)・ハミルトン閉路の出力・オイラー閉路の出力】

【閉路の出力】コード 1/2

reader.on('close', () => {
   const dfs = (now, seen) => {
      const nexts = list[now];
      for (const next of nexts) {
         if (next === s - 1 && seen.length > 2) {
            seen.push(next);
            return seen;
         }
         if (!seen.includes(next)) {
            return dfs(next, [...seen, next]);
         }
      }
   };
   const [n, s] = 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;
   }
   const cycle = dfs(s - 1, [s - 1]);
   console.log(cycle ? cycle.map(e => e + 1).join(' ') : -1);
});
hogeちゃんの画像

閉路… s を出発して s に戻る経路。 同じ頂点を 2 回以上通らない。

【閉路の出力】コード 2/2

reader.on('close', () => {
   const dfs = (now, seen) => {
      const nexts = list[now];
      for (const next of nexts) {
         if (next === s - 1 && seen.length > 2) {
            cycle.push([...seen, next]);
         } else if (seen.includes(next) === false && cycle.length === 0) {
            dfs(next, [...seen, next]);
         }
      }
   };
   const [n, s] = 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;
   }
   const cycle = [];
   if (list[s - 1].length === 1) {
      console.log(-1);
   } else {
      dfs(s - 1, [s - 1]);
      console.log(cycle[0] ? cycle[0].map(e => e + 1).join(' ') : -1);
   }
});
hogeちゃんの画像

閉路… s を出発して s に戻る経路。 同じ頂点を 2 回以上通らない。

【グラフの閉路の総数】コード

reader.on('close', () => {
   const dfs = (now, seen) => {
      const nexts = list[now];
      for (const next of nexts) {
         if (next === s - 1 && seen.length > 2) { 
            total_num++;
         } else if (seen.includes(next) === false) {
            dfs(next, [...seen, next]);
         }
      }
   };
   const [n, s] = 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 total_num = 0;
   if (list[s - 1].length === 1) {
      console.log(0);
   } else {
      dfs(s - 1, [s - 1]);
      console.log(total_num / 2);
   }
});
hogeちゃんの画像

閉路… s を出発して s に戻る経路。 同じ頂点を 2 回以上通らない。

【閉路の出力 2】コード

reader.on('close', () => {
   const dfs = (now, seen) => {
      const nexts = list[now];
      for (const next of nexts) {
         if (next === e1 - 1 && seen.length > 2) {
            cycle.push([...seen, next]);
         }
         if (!seen.includes(next) && cycle.length === 0) {
            dfs(next, [...seen, next]);
         }
      }
   };
   const [n, e1, e2] = 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;
   }
   const cycle = [];
   if (!list[e1 - 1].includes(e2 - 1) || list[e1 - 1].length < 2) {
      console.log(-1);
   } else {
      dfs(e2 - 1, [e1 - 1, e2 - 1]);
      console.log(cycle[0] ? cycle[0].map(e => e + 1).join(' ') : -1);
   }
});
hogeちゃんの画像

dfs() を呼び出す段階で 枝 e を通過済みとしてマークしました。

【グラフの閉路の総数 2】コード

reader.on('close', () => {
   const dfs = (now, seen) => {
      const nexts = list[now];
      for (const next of nexts) {
         if (next === e1 - 1 && seen.length > 2) {
            total_num++;
         } else if (!seen.includes(next)) {
            dfs(next, [...seen, next]);
         }
      }
   };
   const [n, e1, e2] = 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 total_num = 0;
   if (!list[e1 - 1].includes(e2 - 1) || list[e1 - 1].length < 2) {
      console.log(0);
   } else {
      dfs(e2 - 1, [e1 - 1, e2 - 1]);
      console.log(total_num);
   }
});
hogeちゃんの画像
dfs() を呼び出す段階で 枝 e を通過済みとしてマークしました。

【通れない頂点が存在する閉路】コード

reader.on('close', () => {
   const dfs = (now, seen) => {
      const nexts = list[now];
      for (const next of nexts) {
         if (next === t - 1 && seen.length > 2) {
            cycle.push([...seen, next]);
         } 
         if (!seen.includes(next) && !s.includes(next) && cycle.length === 0) {
            dfs(next, [...seen, next]);
         }
      }
   };
   const [n, 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;
   }
   const cycle = [];
   if (list[t - 1].length < 2) {
      console.log(-1);
   } else {
      dfs(t - 1, [t - 1]);
      console.log(cycle[0] ? cycle[0].map(e => e + 1).join(' ') : -1);
   }
});
hogeちゃんの画像

再起関数を呼び出す条件は…

  1. next が通過済みの頂点に含まれない。
  2. next が s  に含まれない。
  3. cycle が空要素。

1〜 3 が全て true の場合になります。

【通れない頂点が存在する閉路の総数】コード

reader.on('close', () => {
   const dfs = (now, seen) => {
      const nexts = list[now];
      for (const next of nexts) {
         if (next === t - 1 && seen.length > 2 + k) {
            total_num++;
         }
         if (!seen.includes(next)) {
            dfs(next, [...seen, next]);
         }
      }
   };
   const [n, 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 total_num = 0;
   if (list[t - 1].length < 2) {
      console.log(0);
   } else {
      dfs(t - 1, [t - 1, ...s]);
      console.log(total_num / 2);
   }
});
hogeちゃんの画像

dfs() を呼び出す段階で 頂点集合 s の要素 を通過済みとしてマークしました。

【ハミルトン閉路の出力】コード

reader.on('close', () => {
   const dfs = (now, seen) => {
      const nexts = list[now];
      for (const next of nexts) {
         if (next === s - 1 && seen.length === n) {
            Hamilton_cycle.push([...seen, next]);
         } else if (!seen.includes(next) && Hamilton_cycle.length === 0) {
            dfs(next, [...seen, next]);
         }
      }
   };
   const [n, s] = 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;
   }
   const Hamilton_cycle = [];
   if (list[s - 1].length === 1) {
      console.log(-1);
   } else {
      dfs(s - 1, [s - 1]);
      console.log(Hamilton_cycle[0]? Hamilton_cycle[0].map(e => e + 1).join(' ') : -1);
   }
});
hogeちゃんの画像

ハミルトン閉路…ある頂点を出発後 残りの全ての頂点を 1 回ずつ通って出発した頂点に戻ってくる経路。

【オイラー閉路の出力】コード

reader.on('close', () => {
   const dfs = (now, cycle, edges) => {
      const nexts = list[now];
      for (const next of nexts) {
         const edge = Math.max(next, now) * 10 + Math.min(next, now);
         if (!edges.includes(edge)) { // 枝 (now,next) が通過済みでないならば
            if (next === s - 1 && cycle.length === V / 2) {
               Euler_cycle.push([...cycle, next]);
            }
            if(Euler_cycle.length === 0){
               dfs(next, [...cycle, next], [...edges, edge]);
            }
         }
      }
   };
   const [n, s] = lines.shift().split(' ').map(Number);
   const list = new Array(n);
   let V = 0;
   for (let i = 0; i < n; i++) {
      const v = Number(lines.shift());
      V += v;
      const a = lines.shift().split(' ').map(e => e - 1);
      list[i] = a;
   }
   const Euler_cycle = [];
   dfs(s - 1, [s - 1], []);
   console.log(Euler_cycle[0].map(e => e + 1).join(' '));
});
hogeちゃんの画像

オイラー閉路…ある頂点を出発後 残りの全ての枝を 1 回ずつ通って出発した頂点に戻ってくるトレイル。

コメント