用javascript 实现邻接矩阵转可达矩阵

邻接矩阵是一种表示图的方式，其中矩阵中的每个元素表示两个节点之间是否存在一条边。可达矩阵是邻接矩阵的一种变换，其中矩阵中的每个元素表示一个节点是否能到达另一个节点。

以下是用 JavaScript 实现邻接矩阵转可达矩阵的代码：

function convertToReachableMatrix(adjMatrix) {
  let n = adjMatrix.length;
  let reachMatrix = [];
  
  // 初始化可达矩阵
  for (let i = 0; i < n; i++) {
    reachMatrix[i] = [];
    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]);
      }
    }
  }
  
  return reachMatrix;
}

// 示例
let adjMatrix = [
  [0, 1, 1, 0],
  [1, 0, 0, 1],
  [0, 1, 0, 1],
  [0, 0, 0, 1]
];
let reachMatrix = convertToReachableMatrix(adjMatrix);
console.log(reachMatrix);

在上述代码中，我们首先初始化可达矩阵为邻接矩阵。然后使用 Floyd-Warshall 算法计算可达矩阵。Floyd-Warshall 算法使用动态规划思想，依次计算每个节点对之间的最短路径，并更新可达矩阵中的值。最后返回可达矩阵即可。