Created
July 9, 2018 15:01
-
-
Save foobic/1865585e7d17a69a6a1d90a1869b14f1 to your computer and use it in GitHub Desktop.
Задача 107: Основы графов. Дана матрица размерности NxN, ктр состоит из нулей и единиц. Необходимо определить является ли она матрицей смежности простого неориентированного графа.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Матрица смежности неориентированного графа всегда симметрична. | |
// Если строка в матрице нулевая, то матрица не является матрицей смежности графа. | |
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й - какой результат хотим увидеть. Ничего, если нужен рандом |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment