Задача 107: Основы графов. Дана матрица размерности NxN, ктр состоит из нулей и единиц. Необходимо определить является ли она матрицей смежности простого неориентированного графа.

task107.js

// Матрица смежности неориентированного графа всегда симметрична.
// Если строка в матрице нулевая, то матрица не является матрицей смежности графа.
let sum = (a, b) => a + b
function isNotOrientedGraph(arr){
  let i, j, flag; 
  for(i = 0; i < arr.length; i++){
      if (arr[i].reduce(sum) === 0) return false // проверка суммы строки матрицы
      if (arr[i][i] === 1) return false // простой граф не имеет петель
      if (arr[i].length !== arr.length) return false // проверка размерности
      for(j = i+1; j < arr.length; j++){
        if(arr[i][j] != arr[j][i]) return false // проверка на симметричность
      }
  }
  return true;
}


// Тесты
let prettyPrint = (arr) => arr.map( row => console.log(row) )
let getRandomInt = (min, max) => Math.floor(Math.random() * (max - min + 1)) + min;

function generateRandomMatrix(n){
  let arr = [];
  for(let i = 0; i < n; i++){
    arr.push([])
    for(let j = 0; j < n; j++){
      // всегда без петель.
      i === j  ? arr[i].push(0) : arr[i].push(Math.round(Math.random()))
      // не всегда без петель 
      // arr[i].push(Math.round(Math.random())
    }
  }
  return arr
}


function test(n, flag){
  let randMatrix, result;
  for(let i = 0; i < n; i++){
    randMatrix = generateRandomMatrix(getRandomInt(2, 4))
    result = isNotOrientedGraph(randMatrix)
    if(flag !== undefined && flag !== result) continue
    console.log('-----')
    prettyPrint(randMatrix)
    console.log(result)
  }
}
test(30, false) 
// 1й операнд - кол-во тестов, 
// 2й - какой результат хотим увидеть. Ничего, если нужен рандом