用js创建一个方法让用户输入有向图邻接矩阵判断是否为简单有向图
时间: 2024-01-03 15:05:25 浏览: 33
首先,我们需要了解什么是简单有向图和有向图邻接矩阵。
简单有向图是指没有自环和重边的有向图,即每个节点之间只有一条有向边。
有向图邻接矩阵是一个二维矩阵,其中第i行第j列的元素表示从节点i到节点j是否有一条有向边。如果有,则为1,否则为0。
下面是一个用JS实现判断简单有向图的邻接矩阵的方法:
```js
function isSimpleDirectedGraph(adjMatrix) {
const n = adjMatrix.length;
// 检查是否有自环和重边
for (let i = 0; i < n; i++) {
if (adjMatrix[i][i] === 1) {
return false; // 存在自环
}
for (let j = 0; j < n; j++) {
if (adjMatrix[i][j] === 1 && adjMatrix[j][i] === 1) {
return false; // 存在重边
}
}
}
return true;
}
```
该方法接受一个邻接矩阵作为参数,返回一个布尔值,表示该邻接矩阵是否为简单有向图。首先,我们检查是否存在自环和重边,如果存在则返回false。如果不存在,则返回true,表示该邻接矩阵为简单有向图。
相关问题
用js让用户通过输入有向图的邻接矩阵并判断它是否是简单的有向图
以下是一个简单的实现,用户需要输入一个二维数组(邻接矩阵),代码会判断这个矩阵是否表示一个简单的有向图。
```javascript
function isSimpleDirectedGraph(adjMatrix) {
// 检查矩阵是否是方阵
if (adjMatrix.length !== adjMatrix[0].length) {
return false;
}
// 检查对角线上的元素是否都为0
for (let i = 0; i < adjMatrix.length; i++) {
if (adjMatrix[i][i] !== 0) {
return false;
}
}
// 检查矩阵是否对称
for (let i = 0; i < adjMatrix.length; i++) {
for (let j = 0; j < adjMatrix[0].length; j++) {
if (adjMatrix[i][j] !== adjMatrix[j][i]) {
return false;
}
}
}
// 检查矩阵是否有重边或自环
for (let i = 0; i < adjMatrix.length; i++) {
for (let j = 0; j < adjMatrix[0].length; j++) {
if (adjMatrix[i][j] > 1 || adjMatrix[i][j] < 0 || i === j) {
return false;
}
}
}
// 如果以上条件都不满足,则表示输入的矩阵是一个简单的有向图
return true;
}
// 示例输入
const adjMatrix = [
[0, 1, 1],
[1, 0, 0],
[0, 1, 0],
];
// 判断结果
console.log(isSimpleDirectedGraph(adjMatrix)); // true
```
该函数的实现思路如下:
1. 首先检查矩阵是否是方阵,如果不是,则不是有向图。
2. 接着检查对角线上的元素是否都为0,如果不是,则存在自环,不是简单图。
3. 然后检查矩阵是否对称,如果不是,则存在重边,不是简单图。
4. 最后检查矩阵是否有重边或自环,如果有,则不是简单图;否则就是简单图。
该函数并不完美,仍有可能出现错误,但对于大部分情况来说已经足够准确。
用js输入邻接矩阵判断是否为有向图
以下是用 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`。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![py](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)