隣接行列の入力・辺の存在判定《グラフ理論》

グラフ構造の入力メニュー【隣接行列の出力(無向グラフ,有向グラフ)・隣接行列の入力(辺の個数,辺の存在判定)】

問題【STEP: 1】隣接行列の出力・無向グラフ
Task
無向グラフの頂点の情報が与えられるので隣接行列を出力してね。

【STEP: 1】コード

reader.on('close', () => {
   function adjacency_Matrix(a, b) {  // 隣接行列の値を更新
      Matrix[a][b]++;
      Matrix[b][a]++;
   }
   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);
   Matrix.forEach(value => {
      console.log(value.join(' '));
   });
});
hogeちゃんの画像

いくつかの頂点と それらのうち 2 つの頂点を結ぶ辺の集合をグラフ(辺に向きがつけられていない場合は無向グラフ)。だそうです。

木のメニューを先にクリアしたので すぐにできた。こっちを先にすべきだったのかな

top
問題【STEP: 2】隣接行列の出力・有向グラフ
Task
有向グラフの頂点の情報が与えられるので隣接行列を出力してね。

【STEP: 2】コード

reader.on('close', () => {
   function adjacency_Matrix(a, b) {  // 隣接行列の値を更新
      Matrix[a][b]++;
   // Matrix[b][a]++;  // 有向なので b→a 方向には繋がらない
   }
   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);
   Matrix.forEach(value => {
      console.log(value.join(' '));
   });
});
hogeちゃんの画像

辺に向きがつけられている場合は有向グラフ。

top
問題【STEP: 3】隣接行列の入力・辺の個数
Task
隣接行列( n 行 n 列 の整数)が与えられるので辺の個数を求めてね。

【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));
   }
  // console.table(Matrix);
   let connected = 0; Matrix.forEach(value => {
      connected += value.reduce((acc, cur) => acc + cur);
   });
   console.log(connected / 2);
});
hogeちゃんの画像

辺の数 = 頂点の数の総数 ÷ ２

top
問題【FINAL】問題
Task
隣接行列( N 行 N 列 の整数) の頂点 (A_i ,B_i) は辺で繋がっている？

【FINAL】コード

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

与えられた隣接行列の情報を Matrix (配列)で受け取り Matrix[A][B] の値を出力すればOK。

top

コメント