用js(1)输入有向图的邻接矩阵来判断它是否是简单的有向图。 (2)输出每个顶点的输入和输出度数。 (3)使用两种方式输入数据,一种方式来自控制台,另一种方式来自CSV文件。
时间: 2024-05-10 18:21:21 浏览: 67
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路
5星 · 资源好评率100%
1. 判断有向图是否简单:
```javascript
function isSimpleDirectedGraph(adjacencyMatrix) {
for (let i = 0; i < adjacencyMatrix.length; i++) {
for (let j = 0; j < adjacencyMatrix.length; j++) {
if (adjacencyMatrix[i][j] > 1) {
return false; // 如果有多条边连接同一个顶点,则不是简单有向图
}
if (i === j && adjacencyMatrix[i][j] !== 0) {
return false; // 如果有环,则不是简单有向图
}
}
}
return true;
}
```
2. 输出每个顶点的输入和输出度数:
```javascript
function calculateInOutDegrees(adjacencyMatrix) {
const degrees = [];
for (let i = 0; i < adjacencyMatrix.length; i++) {
let inDegree = 0;
let outDegree = 0;
for (let j = 0; j < adjacencyMatrix.length; j++) {
if (adjacencyMatrix[j][i] === 1) {
inDegree++; // 统计入度
}
if (adjacencyMatrix[i][j] === 1) {
outDegree++; // 统计出度
}
}
degrees.push({ vertex: i, inDegree, outDegree });
}
return degrees;
}
```
3. 使用控制台输入:
```javascript
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.question('请输入有向图的邻接矩阵,以逗号分隔:\n', (input) => {
const adjacencyMatrix = input.split(',').map(str => parseInt(str));
const n = Math.sqrt(adjacencyMatrix.length);
const matrix = [];
for (let i = 0; i < n; i++) {
matrix.push(adjacencyMatrix.slice(i * n, (i + 1) * n));
}
if (isSimpleDirectedGraph(matrix)) {
console.log('这是一个简单有向图');
console.log('每个顶点的输入和输出度数为:');
console.table(calculateInOutDegrees(matrix));
} else {
console.log('这不是一个简单有向图');
}
rl.close();
});
```
4. 使用CSV文件输入:
```javascript
const fs = require('fs');
const parse = require('csv-parse');
fs.readFile('data.csv', (err, fileData) => {
if (err) {
console.error(err);
return;
}
parse(fileData, { delimiter: ',' }, (err, rows) => {
if (err) {
console.error(err);
return;
}
const adjacencyMatrix = rows.map(row => row.map(str => parseInt(str)));
if (isSimpleDirectedGraph(adjacencyMatrix)) {
console.log('这是一个简单有向图');
console.log('每个顶点的输入和输出度数为:');
console.table(calculateInOutDegrees(adjacencyMatrix));
} else {
console.log('这不是一个简单有向图');
}
});
});
```
阅读全文