求传递闭包的 Warshall 算法详解

过程详情

【例子】关系的矩阵是：

求传递闭包。

【分析与解答】

我们看第 1 列：$\pmatrix{0\\1\\1\\0}$。

$\pmatrix{\color{red}0\\1\\1\\0}$ $a_{11}=0$ 跳过。

$\pmatrix{0\\\color{blue}1\\1\\0}$ $a_{\color{green}2\color{red}1}=1$，则 $a_{\color{red}1}$ 行加到 $a_{\color{green}2}$ 行：

得到：

$\pmatrix{0\\1\\\color{blue}1\\0}$，$a_{31} = 1$，则 $a_1$ 行加到 $a_3$ 行，得到：

$\pmatrix{0\\1\\1\\\color{red}0}$，$a_{41} = 0$，跳过。

接下来是第二列（注意：不是原矩阵的第二列，而是上面处理后最后的矩阵的第二列，下同）：

我们看第 2 列：$\pmatrix{0\\0\\0\\0}$。全是零，意味着 $a_{i2}$ 都跳过处理。

我们看第 3 列：$\pmatrix{0\\1\\0\\1}$

注意到 $a_{23} = 1$，则 $a_3$ 行加到 $a_2$ 行，得到：

注意到 $a_{43} = 1$，则 $a_3$ 行加到 $a_4$ 行，得到：

我们看第 4 列：$\pmatrix{1\\1\\1\\1}$

注意到 $a_{14}\sim a_{44} = 1$，也就是 $a_4$ 行依次加到上面各行：

这就是最终正确答案。

例题

【例子】计算传递闭包之于：

【分析与解答】

按列从左到右，每列按行从上到下扫描：

$(4,1) = 1$，故：

$(1,2) = 1$，故：

$(4,2) = 1$，故：

$(4,3) = 1$，故：

$(1,4) = 1$，故：

$(2,4) = 1$，故：

$(4,4) = 1$，故：

🦔最终解。