多重辺・自己ループ《グラフ理論》

グラフ構造の入力メニュー【自己ループ[無向グラフ,有向グラフ(辺入力)]・多重辺[無向グラフ,有向グラフ (辺入力)) 】

問題【STEP: 1】自己ループ・無向グラフ
Task
無向グラフの「自己ループ」の辺が存在する頂点をすべて出力してね。

【STEP: 1】コード

reader.on('close', () => {
   const Matrix = [];  // 隣接行列
   const N = Number(lines[0]);
   for (let i = 1; i <= N; i++) {
      Matrix.push(lines[i].split(' ').map(Number));
   }
   const self_loop = [0];
   for (let i = 0; i < N; i++) {
      if (Matrix[i][i]) {
         self_loop[0]++;
         self_loop.push(i + 1);
      }
   }
   self_loop.forEach(value => {
      console.log(value);
   });
});
hogeちゃんの画像

隣接行列…n × n の２次元配列。頂点 i ・ j  が 辺で直接つながっていれば i 行目 j 列目の要素を１。さもなくば 0。

top
問題【STEP: 2】多重辺・無向グラフ
Task
無向グラフの「多重辺」の存在する頂点の組をすべて出力してね。

【STEP: 2】コード

reader.on('close', () => {
   const Matrix = [];  // 隣接行列
   const N = Number(lines[0]);
   for (let i = 1; i <= N; i++) {
      Matrix.push(lines[i].split(' ').map(Number));
   }
   // console.log(Matrix);
   const multiple_sides = [
      [0]
   ];
   for (let i = 0; i < N; i++) {
      for (let j = 0; j < N; j++) {
         if (Matrix[i][j] >= 2) {
            multiple_sides[0][0]++;
            multiple_sides.push([i + 1, j + 1]);
            Matrix[j][i] = 0;
         }
      }
   }
   multiple_sides.forEach(value => {
      console.log(...value);
   });
});
hogeちゃんの画像

多重辺…グラフの同じ頂点の組をつなげている複数の辺。
つまり 2車線とか3車線みたいな感じ？

top
問題【STEP: 3】自己ループ・有向グラフ
Task
有向グラフの「自己ループ」の辺が存在する頂点をすべて出力してね。

【STEP: 3】コード

reader.on('close', () => {
   const Matrix = [];  // 隣接行列
   const N = Number(lines[0]);
   for (let i = 1; i <= N; i++) {
      Matrix.push(lines[i].split(' ').map(Number));
   }
   const self_loop = [0];
   for (let i = 0; i < N; i++) {
      if (Matrix[i][i]) {
         self_loop[0]++;
         self_loop.push(i + 1);
      }
   }
   self_loop.forEach(value => {
      console.log(value);
   });
});
hogeちゃんの画像

自己ループ…入口と出口が同じで 直結しているってことですよね。

top
問題【STEP: 4】多重辺・有向グラフ
Task
ね。

【STEP: 4】コード

reader.on('close', () => {
   function adjacency_Matrix(a, b) {
      Matrix[a][b]++;
   }
   const Matrix = [];  // 隣接行列
   const [N, M] = lines[0].split(' ').map(Number);
   for (let i = 0; i < N; i++) {
      Matrix[i] = new Array(N).fill(0);
   }
   for (let i = 1; i < M; i++) {
      const [A, B] = lines[i].split(' ').map(e => e - 1);
      adjacency_Matrix(A, B);
   }
   // console.log(Matrix);
   const self_loop = [0];
   for (let i = 0; i < N; i++) {
      if (Matrix[i][i]) {
         self_loop[0]++;
         self_loop.push(i + 1);
      }
   }
   self_loop.forEach(value => {
      console.log(value);
   });
});
hogeちゃんの画像
多重辺有向グラフ…辺が同じ方向に向かっていても 行き違っていても 辺が 2本以上あれば多重線。
top
問題【STEP: 5】自己ループ・有向グラフ(辺入力)
Task
有向グラフの「自己ループ」の辺が存在する頂点をすべて出力してね。

【STEP: 5】コード

reader.on('close', () => {
   function adjacency_Matrix(a, b) {
      Matrix[a][b]++;
   }
   const Matrix = []; // 隣接行列
   const [N, M] = lines[0].split(' ').map(Number);
   for (let i = 0; i < N; i++) {
      Matrix[i] = new Array(N).fill(0);
   }
   for (let i = 1; i < M; i++) {
      const [A, B] = lines[i].split(' ').map(e => e - 1);
      adjacency_Matrix(A, B);
   }
   // console.log(Matrix);
   const multiple_sides = [
      [0]
   ];
   for (let i = 0; i < N; i++) {
      for (let j = 0; j < N; j++) {
         if (Matrix[i][j] >= 2 || (Matrix[i][j] && Matrix[j][i])) {
            multiple_sides[0][0]++;
            multiple_sides.push([i + 1, j + 1]);
            Matrix[j][i] = 0;
         }
      }
   }
   multiple_sides.forEach(value => {
      console.log(...value);
   });
});
hogeちゃんの画像

入力値を基に 隣接行列を生成して 「自己ループ」の辺を持つ頂点を探索。

top
問題【FINAL】多重辺・有向グラフ(辺入力)
Task
有向グラフの「多重辺」の存在する頂点の組をすべて出力してね。ね。

【FINAL】コード

reader.on('close', () => {
   function adjacency_Matrix(a, b) {  // 隣接行列の値を更新
      Matrix[a][b]++;
   }
   const Matrix = [];  // 隣接行列
   const [N, M] = lines[0].split(' ').map(Number);
   for (let i = 0; i < N; i++) {
      Matrix[i] = new Array(N).fill(0);
   }
   for (let i = 1; i <= M; i++) {
      const [A, B] = lines[i].split(' ').map(e => e - 1);
      adjacency_Matrix(A, B);
   }
  // console.table(Matrix);
   const multiple_sides = [
      [0]
   ];
   for (let i = 0; i < N; i++) {
      for (let j = 0; j < N; j++) {
         if (Matrix[i][j] >= 2 || (Matrix[i][j] && Matrix[j][i])) {
            multiple_sides[0][0]++;
            multiple_sides.push([i + 1, j + 1]);
            Matrix[j][i] = 0;
         }
      }
   }
   multiple_sides.forEach(value => {
      console.log(...value);
   });
});
hogeちゃんの画像

入力値を基に 隣接行列を生成して 「多重辺」の存在する頂点の組を探索。

コメント