次数が 2 以下の全域木の出力《グラフ・DFS》

グラフ・DFSメニュー【全域木の判定・全域木の出力 １〜３・次数が 2 以下の全域木の出力】

問題【STEP: 1】全域木の判定
Task
n 個の頂点からなる無向グラフの隣接リストは全域木を現している？  Yes ・No を出力してね。

【全域木の判定】コード

reader.on('close', () => {
   const dfs = (now, seen) => {  // (現在地, 訪問済)
      const nexts = list[now];  // 隣接している頂点
      for (const next of nexts) {  // 隣接している各頂点が…
         if (!seen.includes(next)) {  // 未訪問なら…
            seen.push(next);  // 訪問済にする
            dfs(next, seen);  // next に移動
         }
      }
      return seen.length;  // seen の要素数を返す
   };
   const n = Number(lines.shift());
   const list = new Array(n).fill().map(e => []);
   let edge_num = 0;  // 枝の数
   for (let i = 0; i < n; i++) {
      const v = Number(lines.shift());  // 隣接している頂点の数
      edge_num += v;
      const a = lines.shift().split(' ').map(e => e - 1);
      list[i] = a;
   }
   if (n - edge_num / 2 === 1) {  // 頂点数 - 枝の数 / 2 が 1 なら…
      console.log(dfs(0, [0]) === n ? 'Yes' : 'No');
   } else {
      console.log('No');
   }
});
hogeちゃんの画像

全域木…全域部分グラフ（そのグラフの全頂点を含む部分グラフ）のうち、木（連結で閉路を持たないグラフ）であるものをいう。(ウィキペディア)

top
問題【STEP: 2】全域木の出力
Task
n 個の頂点からなる無向グラフの隣接リストから枝を n-1 個選んで全域木を構成してね。

【全域木の出力】コード

reader.on('close', () => {
   const dfs = (now, seen, edges) => {  // (現在地, 訪問済, 枝)
      const nexts = list[now];
      for (const next of nexts) {
         if (!seen.includes(next)) {
            seen.push(next);
            edges.push([now, next]);  // 現在地 と 次の頂点のペアを保存
            dfs(next, seen, edges);
         }
      }
      return edges;
   };
   const n = Number(lines.shift());
   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 Edges = dfs(0, [0], []);
   Edges.forEach(edge => {
      console.log(...edge.map(e => e + 1));
   });
});
hogeちゃんの画像

next が 未訪問なら[now, next ]を edges に保存。

top
問題【STEP: 3】全域木の出力 2
Task
無向グラフの隣接リストから 枝集合 E に含まれない枝を n-1 個選んで全域木を構成してね。

【全域木の出力 2】コード

reader.on('close', () => {
   const dfs = (now, seen, edges = []) => {
      const nexts = list[now];
      for (const next of nexts) {
         if (!seen.includes(next)) {
            seen.push(next);
            edges.push([now, next]);
            dfs(next, seen, edges);
         }
      }
      return edges;
   };
   const n = Number(lines.shift());
   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 k = Number(lines.shift());
   for (let i = 0; i < k; i++) {
      const [e, d] = lines.shift().split(' ').map(e => e - 1);
      const e_d = list[e].indexOf(d);
      const d_e = list[d].indexOf(e);
      list[e].splice(e_d, 1);
      list[d].splice(d_e, 1);
   }
   const Edges = dfs(0, [0]);
   if (Edges.length === n - 1) {
      Edges.forEach(edge => {
         console.log(...edge.map(e => e + 1));
      });
   } else {
      console.log(-1);
   }
});
hogeちゃんの画像

E に含まれる枝を予め list から削除してから dfs() を呼び出しました。

top
問題【STEP: 4】全域木の出力 3
Task
 隣接リスト(自己ループ・多重辺無) と頂点集合 S が与えられるので S の頂点を除いた全ての頂点を含む木を出力してね。

【全域木の出力 3 】コード

reader.on('close', () => {
   const dfs = (now, seen) => {
      const nexts = list[now];
      for (const next of nexts) {
         if (!seen.includes(next)) {
            edges.push([now, next]);
            seen.push(next);
            dfs(next, seen);
         }
      }
  };
   const n = Number(lines.shift());
   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 node = n - k - 1;
   const edges = [];
   dfs(0,[0,...S]);
   if (edges.length === node) {
      for (const edge of edges) {
         console.log(...edge.map(e => e + 1));
      }
   }else {
      console.log(-1);
   }
});
hogeちゃんの画像
S  に含まれる頂点は予め通過済みとしてから dfs() を呼び出しました。
top
問題【FINAL】次数が 2 以下の全域木の出力
Task
隣接リストから枝を n-1 個選び 各頂点の次数が 2 以下となるような全域木を構成してね。

【次数が 2 以下の全域木の出力】コード 92点

reader.on('close', () => {
   const dfs = (now, seen) => {
      const nexts = list[now];
      for (const next of nexts) {
         if (!seen.includes(next)) {
            edges.push([now, next]);
            return dfs(next, [...seen, next]);
         }
      }
   };
   const n = Number(lines.shift());
   const list = new Array(n).fill().map(e => []);
   const start = [];
   for (let i = 0; i < n; i++) {
      const v = Number(lines.shift());
      if (v === 1) {
         start.push(i);
      }
      const a = lines.shift().split(' ').map(e => e - 1);
      list[i] = a;
   }
   const edges = [];
  if (start.length > 0 && start.length < 3) {
      dfs(start[0], [start[0]]);
   } else {
      for (let i = 0; i < n; i++) {
         dfs(i, [i]);
         
         if (edges.length === n - 1) {
            break;
         } else {
            edges.length = 0;
         }
      }
   }
   if (edges.length === n - 1) {
      for(const edge of edges){
          console.log(...edge.map(e =>e+1));
      }
   } else {
      console.log(-1);
   }
});
hogeちゃんの画像

100点にできなかった。(´·ω·`)

top

コメント