用js输入邻接矩阵判断是否为有向图
时间: 2024-05-09 11:20:11 浏览: 5
以下是用 JavaScript 实现判断邻接矩阵是否为有向图的代码:
```javascript
function isDirectedGraph(adjMatrix) {
// 获取矩阵的行数和列数
const rows = adjMatrix.length;
const cols = adjMatrix[0].length;
// 判断矩阵是否方阵
if (rows !== cols) {
return false;
}
// 遍历矩阵,判断是否为有向图
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
// 如果 i 和 j 相等,即自环边,跳过
if (i === j) {
continue;
}
// 如果 i 和 j 不相等,但是 adjMatrix[i][j] 和 adjMatrix[j][i] 均为 1,即存在双向边,返回 false
if (adjMatrix[i][j] === 1 && adjMatrix[j][i] === 1) {
return false;
}
}
}
// 如果遍历完矩阵没有返回 false,则为有向图,返回 true
return true;
}
// 测试
const adjMatrix = [
[0, 1, 0],
[0, 0, 1],
[0, 0, 0]
];
console.log(isDirectedGraph(adjMatrix)); // 输出 true
const adjMatrix2 = [
[0, 1, 1],
[1, 0, 1],
[1, 1, 0]
];
console.log(isDirectedGraph(adjMatrix2)); // 输出 false
```
以上代码中,`isDirectedGraph` 函数接收一个邻接矩阵作为参数,然后判断该矩阵是否为有向图。如果是有向图,则返回 `true`,否则返回 `false`。函数的实现过程是:
1. 首先获取矩阵的行数和列数,如果不相等则不是方阵,直接返回 `false`。
2. 然后遍历矩阵,对于每一个不为自环边的节点对 $(i,j)$,如果 `adjMatrix[i][j]` 和 `adjMatrix[j][i]` 均为 1,即存在双向边,返回 `false`。
3. 如果遍历完矩阵没有返回 `false`,则说明矩阵为有向图,返回 `true`。
在测试中,我们分别测试了一个有向图和一个无向图的邻接矩阵。第一个矩阵的第一行表示节点 1 有一条指向节点 2 的边,第二行表示节点 2 有一条指向节点 3 的边,因此矩阵为有向图,输出 `true`。而第二个矩阵的第一行表示节点 1 有一条指向节点 2 的边和一条指向节点 3 的边,第二行表示节点 2 有一条指向节点 1 的边和一条指向节点 3 的边,因此矩阵为无向图,输出 `false`。