求传递闭包的 Warshall 算法详解
过程详情
【例子】关系的矩阵是： $$ \boldsymbol{W}_{0}=\left[\begin{array}{llll} 0 & 0 & 0 & 1 \ 1 & 0 & 1 & 0 \ 1 & 0 & 0 & 1 \ 0 & 0 & 1 & 0 \end{array}\right] $$ 求传递闭包。
【分析与解答】
我们看第 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}$ 行： $$ \boldsymbol{W}=\left[\begin{array}{llll} \color{blue}0 & \color{blue}0 & \color{blue}0 & \color{blue}1 \ 1+\color{blue}0 & 0+\color{blue}0 & 1+\color{blue}0 & 0+\color{blue}1 \ 1 & 0 & 0 & 1 \ 0 & 0 & 1 & 0 \end{array}\right] $$ 得到： $$ \boldsymbol{W}=\left[\begin{array}{llll} 0 & 0 & 0 & 1 \ 1 & 0 & 1 & 1 \ 1 & 0 & 0 & 1 \ 0 & 0 & 1 & 0 \end{array}\right] $$ $\pmatrix{0\1\\color{blue}1\0}$，$a_{31} = 1$，则 $a_1$ 行加到 $a_3$ 行，得到：
$$ \boldsymbol{W}=\left[\begin{array}{llll} 0 & 0 & 0 & 1 \ 1 & 0 & 1 & 1 \ 1 & 0 & 0 & 1 \ 0 & 0 & 1 & 0 \end{array}\right] $$ $\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$ 行，得到： $$ \boldsymbol{W}=\left[\begin{array}{llll} 0 & 0 & 0 & 1 \ 1 & 0 & 1 & 1 \ 1 & 0 & 0 & 1 \ 0 & 0 & 1 & 0 \end{array}\right] $$
注意到 $a_{43} = 1$，则 $a_3$ 行加到 $a_4$ 行，得到： $$ \boldsymbol{W}=\left[\begin{array}{llll} 0 & 0 & 0 & 1 \ 1 & 0 & 1 & 1 \ 1 & 0 & 0 & 1 \ 1 & 0 & 1 & 1 \end{array}\right] $$
我们看第 4 列：$\pmatrix{1\1\1\1}$
注意到 $a_{14}\sim a_{44} = 1$，也就是 $a_4$ 行依次加到上面各行： $$ \boldsymbol{W}=\left[\begin{array}{llll} 1 & 0 & 1 & 1 \ 1 & 0 & 1 & 1 \ 1 & 0 & 0 & 1 \ 1 & 0 & 1 & 1 \end{array}\right] $$
$$ \boldsymbol{W}=\left[\begin{array}{llll} 1 & 0 & 1 & 1 \ 1 & 0 & 1 & 1 \ 1 & 0 & 0 & 1 \ 1 & 0 & 1 & 1 \end{array}\right] $$
$$ \boldsymbol{W}=\left[\begin{array}{llll} 1 & 0 & 1 & 1 \ 1 & 0 & 1 & 1 \ 1 & 0 & 1 & 1 \ 1 & 0 & 1 & 1 \end{array}\right] $$
$$ \boldsymbol{W}=\left[\begin{array}{llll} 1 & 0 & 1 & 1 \ 1 & 0 & 1 & 1 \ 1 & 0 & 1 & 1 \ 1 & 0 & 1 & 1 \end{array}\right] $$
这就是最终正确答案。
例题
【例子】计算传递闭包之于： $$ \boldsymbol{A}= \begin{bmatrix} 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 0 & 0 \ 1 & 0 & 1 & 0 \end{bmatrix} $$ 【分析与解答】
按列从左到右，每列按行从上到下扫描：
$(4,1) = 1$，故： $$ \boldsymbol{T}= \begin{bmatrix} 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 0 & 0 \ 1 & 1 & 1 & 0 \end{bmatrix} $$ $(1,2) = 1$，故： $$ \boldsymbol{T}= \begin{bmatrix} 0 & 1 & 0 & 1 \ 0 & 0 & 0 & 1 \ 0 & 0 & 0 & 0 \ 1 & 1 & 1 & 0 \end{bmatrix} $$ $(4,2) = 1$，故： $$ \boldsymbol{T}= \begin{bmatrix} 0 & 1 & 0 & 1 \ 0 & 0 & 0 & 1 \ 0 & 0 & 0 & 0 \ 1 & 1 & 1 & 1 \end{bmatrix} $$ $(4,3) = 1$，故： $$ \boldsymbol{T}= \begin{bmatrix} 0 & 1 & 0 & 1 \ 0 & 0 & 0 & 1 \ 0 & 0 & 0 & 0 \ 1 & 1 & 1 & 1 \end{bmatrix} $$ $(1,4) = 1$，故： $$ \boldsymbol{T}= \begin{bmatrix} 1 & 1 & 1 & 1 \ 0 & 0 & 0 & 1 \ 0 & 0 & 0 & 0 \ 1 & 1 & 1 & 1 \end{bmatrix} $$ $(2,4) = 1$，故： $$ \boldsymbol{T}= \begin{bmatrix} 1 & 1 & 1 & 1 \ 1 & 1 & 1 & 1 \ 0 & 0 & 0 & 0 \ 1 & 1 & 1 & 1 \end{bmatrix} $$ $(4,4) = 1$，故： $$ \boldsymbol{T}= \begin{bmatrix} 1 & 1 & 1 & 1 \ 1 & 1 & 1 & 1 \ 0 & 0 & 0 & 0 \ 1 & 1 & 1 & 1 \end{bmatrix} $$ 🦔最终解。