TOC
传递闭包
传递闭包、即在数学中，在集合 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），中文亦称弗洛伊德算法，是解决任意两点间的最短路径的一种算法[1]，可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题，同时也被用于计算有向图的传递闭包[2]。
一个非常简单的动态规划算法，其核心理念为内部顶点限制的扩张。有点类似与一种广度优先扩张算法，不断的放宽条件进行迭代。
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
}