用javascript 实现邻接矩阵转可达矩阵并计算层级
时间: 2024-02-09 22:13:40 浏览: 18
以下是修改后的代码,实现邻接矩阵转可达矩阵,并计算节点的层级。
```javascript
function convertToReachableMatrix(adjMatrix) {
let n = adjMatrix.length;
let reachMatrix = [];
let level = [];
// 初始化可达矩阵和层级
for (let i = 0; i < n; i++) {
reachMatrix[i] = [];
level[i] = -1;
for (let j = 0; j < n; j++) {
reachMatrix[i][j] = adjMatrix[i][j];
}
}
// Floyd-Warshall 算法计算可达矩阵
for (let k = 0; k < n; k++) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
reachMatrix[i][j] = reachMatrix[i][j] || (reachMatrix[i][k] && reachMatrix[k][j]);
}
}
}
// 计算节点的层级
let visited = new Set();
let queue = [];
level[0] = 0;
visited.add(0);
queue.push(0);
while (queue.length > 0) {
let curr = queue.shift();
for (let i = 0; i < n; i++) {
if (reachMatrix[curr][i] && !visited.has(i)) {
level[i] = level[curr] + 1;
visited.add(i);
queue.push(i);
}
}
}
return { reachMatrix, level };
}
// 示例
let adjMatrix = [
[0, 1, 1, 0],
[1, 0, 0, 1],
[0, 1, 0, 1],
[0, 0, 0, 1]
];
let { reachMatrix, level } = convertToReachableMatrix(adjMatrix);
console.log(reachMatrix);
console.log(level);
```
在上述代码中,我们新增了一个 `level` 数组,用于保存每个节点的层级。在初始化可达矩阵和层级时,将 `level` 数组的每个元素都初始化为 -1。接着,在计算可达矩阵后,使用 BFS 算法计算每个节点的层级。具体来说,我们从节点 0 开始,将其加入队列,并将其层级设为 0。然后,依次从队列中取出每个节点,并遍历其所有邻居节点。如果邻居节点尚未被访问过,则将其层级设为当前节点层级加 1,并将其加入队列和已访问集合中。最后返回可达矩阵和层级即可。
注意:上述代码假设图中节点从 0 开始编号。如果节点编号从 1 开始,则需要相应地修改代码。