Warshall 算法求传递闭包

传递闭包

传递闭包、即在数学中，在集合 X 上的二元关系 R 的传递闭包是包含 R 的 X 上的最小的传递关系。 例如，如果 X 是(生或死)人的集合而 R 是关系“为父子”，则 R 的传递闭包是关系“x 是 y 的祖先”。再比如，如果 X 是空港的集合而关系 xRy 为“从空港 x 到空港 y 有直航”，则 R 的传递闭包是“可能经一次或多次航行从 x 飞到 y”。

设 R 是集合A上的关系。连通性关系 R* 由形如(a,b)的有序对构成，使得在关系R中，从 a 到 b 之间存在一条长度至少为1的路径

假设二元关系 R 代表了纽约所有地铁站之间的直接到达关系，如 (a,b),(b,c) 代表可以从 a 直达b , 从 b 可以直达 c , 从a 也能间接到达 c。 而连通性关系则包涵了 (a,b),(b,c),(a,c) 这样的关系，可以认为是关系的深度挖掘，找出所有节点通过某个路径可到达的所有节点(一种多对多关系)。传递闭包和连通性关系可以被认为是等价的，一旦我们计算出了连通性关系R*也就求出了传递闭包。

关系R的连通性关系 R* = R ∪ R^2 ∪ R^3 … ∪ R^n n = 关系集合中的元素个数

至于延伸到矩阵中的运算这里不做展开。

原始的计算方法

/**
 * @description 计算 A B 布尔矩阵的布尔积
 * @param a 待计算的 A 矩阵
 * @param b 待计算的 B 矩阵
 * @return 返回结果矩阵
 */
function booleanMartixProduct(a: number[][], b: number[][]): number[][] {
  let aRow = a.length
  let bCol = b[0].length
  if (aRow !== bCol) {
    console.log("无法计算矩阵")
    return [[]]
  }

  let res = []
  for (let i = 0; i < aRow; i++) {
    res[i] = []
    for (let j = 0; j < bCol; j++) {
      res[i][j] = booleanVectorProduct(a[i], b.map(v => v[j]))
    }
  }

  return res
}

/**
 * @description 计算两个布尔向量的最终结果 如果a[i] = b[i] = 1 那么结果为1 否则为0
 * @param {[number]} a 待计算的向量 A
 * @param {[number]} b 待计算的向量 B
 * @returns {number} 0 or 1 
 */
function booleanVectorProduct(a: number[], b: number[]): number {
  const lenA = a.length
  const lenB = b.length

  if (lenA !== lenB) {
    console.log("向量布尔积计算失败");
    return null
  }

  for (let i = 0; i < lenA; i++) {
    if (a[i] === 1 && b[i] === 1) {
      return 1
    }
  }

  return 0
}

/**
 * @description 计算两个布尔矩阵的集合运算 传入高阶函数
 *
 * @param {number[][]} a
 * @param {number[][]} b
 * @param {(a: number, b: number) => boolean} cb
 * @returns
 */
function booleanMartixCalc(a: number[][], b: number[][], cb: (a: number, b: number) => boolean) {
  let ai = a.length
  let bi = b.length
  let aj = a[0].length
  let bj = b[0].length

  if (ai !== bi || aj !== bj) {
    console.log("无法计算");
  }


  let res = []
  for (let i = 0; i < ai; i++) {
    res[i] = []
    for (let j = 0; j < aj; j++) {
      res[i][j] = Number(cb(a[i][j], b[i][j]))
    }
  }

  return res
}

/**
 * @description 计算布尔矩阵的并 (Join)
 * @param a 
 * @param b 
 */
function booleanMartixJoin(a: number[][], b: number[][]): number[][] {
  return booleanMartixCalc(a, b, (a, b) => a == 1 || b == 1)
}

/**
 * @description 计算布尔矩阵的交 (Meet)
 * @param a 
 * @param b 
 */
function booleanMartixMeet(a: number[][], b: number[][]): number[][] {
  return booleanMartixCalc(a, b, (a, b) => a == 1 && b == 1)
}

/**
 * 计算一个n*n的矩阵的传递闭包
 * 复杂度 O(n ^ 4)
 * 
 * @param m 
 */
function calcTransitiveClosure(m: number[][]): number[][] {
  let a = m
  let b = a
  let n = m.length

  for (let i = 1; i < n; i++) {
    a = booleanMartixProduct(a, m) // 不断累加布尔积
    b = booleanMartixJoin(a, b) // 做join运算
  }

  return b
}

console.log(calcTransitiveClosure([[1, 0, 1], [0, 1, 0], [1, 1, 0]]));

Warshell算法

Floyd-Warshall算法（Floyd-Warshall algorithm），中文亦称弗洛伊德算法，是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题，同时也被用于计算有向图的传递闭包。

一个非常简单的动态规划算法，其核心理念为内部顶点限制的扩张。有点类似与一种广度优先扩张算法，不断的放宽条件进行迭代。

function warshall(m: number[][]): number[][] {
  let n = m.length
  // m的复制
  let w = m.map(v => v.slice())

  for (let k = 0; k < n; k++) { // 内部顶点的限制 
    for (let i = 0; i < n; i++) { // i
      for (let j = 0; j < n; j++) { // j
        // 最核心的递推公式
        // 情况1 在不把节点k放入内部顶点集合中时， m[i][j] 本身已经是一条可达路径，所以可以直接返回 1
        // 情况2 在不把节点k放入内部顶点集合中时 m[i][k] m[k][j] 都可到达，新增的这个k节点让 w[i][j] 成为一条可以到达的路径 也返回1
        // w 矩阵为 Wk 矩阵 也就是当前准备计算的矩阵 m 为上一个矩阵
        w[i][j] = m[i][j] || (m[i][k] && m[k][j])
      }
    }
    m = w
  }

  return w
}