传递闭包的两种算法实现及比较

发表于 2020-03-19 更新于 2022-04-18 分类于 math 本文字数： 2.7k 阅读时长 ≈ 2 分钟

Warshall算法

假设\(R\)是定义在集合\(A\)上的二元关系，\(S\)是\(R\)的传递闭包.
- Input：二元关系\(R\)的矩阵形式\(M_R\)
- Output: \(R\)对应的传递闭包\(S\).

1. 传递闭包的定义法¹

1.1. 原理分析

由传递闭包的定义可得\(R^i\subset S\)(这里的幂指数\(i\)表示\(i\)个二元关系的合成), 则有

\[ \begin{equation}\label{eq1} S=\bigcup_{i=1}^{\infty}R^i \end{equation} \]

我们对\(\eqref{eq1}\)式继续进行分析，优化可得

\[ \begin{equation} S=\bigcup_{i=1}^nR^i\qquad\text{n是集合A的基数}\label{eq:2} \end{equation} \]

证明：

设\((x,y)\in S\),则必存在一个最小的正整数\(p\)使得\((x,y)\in R^p\)，这就是说存在一个序列\(x,a_1,a_2,a_3,⋯,a_{p−1},y\)

使得\((x,a_1 )\in R,\ (a_1,a_2 )\in R,\ (a_2,a_3 )\in R,\cdots，(a_{p−1},y)\in R\),那么\(a_1\) 到\(a_{p−1}\)必须互不相同且不同于\(x\)和\(y\)，否则关系复合的链条就会缩短，从而与\(p\)的最小性矛盾

因此\(p\)的最大可能值出现在\(x=y\),而\(p−1=n−1\),故得证\(p\le n\),即\(S=\bigcup\limits_{i=1}^nR^i\)⁡

\(\eqref{eq:2}\)式用矩阵的形式表示为

\[ M_s=M_R\lor M_R^{[2]}\lor M_R^{[3]}\cdots\lor M_{R}^{[n]} \]

其中,\(M_R^{[i]}\)表示\(i\)个\(0-1\)矩阵\(M_R\)的布尔积

1.2. 伪代码

procedure transitive closure
A:=M_R
S:=A
for i:=2 to n
    A:=A*M_R;(这里的*表示逻辑积)
    S:=S V A
return S

1.3. 时间复杂度

最后一步需要算\(n-1\)个\(M_R^{[i]}\)的并，计算每一个并运算需要使用\(n^2\)次并运算
计算布尔幂\(M_R^{[i]}\)需要求出\(n-1\)个\(n\times n\)矩阵的布尔积。计算每个布尔积需要使用\(n^2(2n-1)\)次位运算。因此此步共需要\(n^2(2n-1)(n-1)\)次位运算
总共需要\(n^2(2n-1)(n-1)+(n-1)n^2=2n^3(n-1)\)，即该算法的时间复杂度为\(O(n^4)\)

1.4. Matlab代码

注：Matlab可以进行向量化运算，因此实际运行时间会小于\(O(n^4)\)

% main function 
function Ms=closure(Mr)
% get the size of Matrix inputed
n=size(Mr);
temp=zeros(n);
Ms=Mr;
% init
Mrk=Mr;

for k=2:n
    for i=1:n
        for j=1:n
%             vectorize to speed up a little
            temp(i,j)=log_sum(Mrk(i, : )&Mrk(: ,j)');
        end
    end
    Mrk=temp;
    Ms=Ms|Mrk;
end

end

function ls=log_sum(t)
    nn=length(t);
    ls=t(1);
    for i=2:nn
        ls=ls|t(i);
    end
end

2. 沃舍尔算法

这个算法能够高效地计算某个二元关系的传递闭包

2.1. 原理分析

其基础是构造一系列的\(0-1\)矩阵。这些矩阵是\(W_0,W_1,W_2,\cdots,W_n\)，其中\(W_0=M_r\),且\(W_k=[w_{ij}^{(k)}]\)（此处类似于迭代）。\(A=\{v_1,v_2,\cdots,v_n\}\)。
如果存在一条从\(v_i\)到\(v_j\)的路径使得这条路径的内点在集合\(A\)内（就是找到一个点\(v_k\)使得\(w_{ik}=1\)且\(w_{kj}=1\)，即存在路径\(v_i\rightarrow v_k\rightarrow v_j\),有点类似与Floyd算法），则记\(w_{ij}^{(k)}=1\)
\(W_n\)就是所要求的\(S\)
以上是大致的思路。
补充一个引理：

设\(W_k=[w_{ij}^{(k)}]\)是\(0-1\)矩阵，它在\((i,j)\)位置处取1当且仅当存在一条从\(v_{i}\)到\(v_{j}\)的路径，其内部顶点取值集合\(A\),数学语言描述为

\[w_{ij}^{(k)}=w_{ij}^{(k-1)}\lor(w_{ik}^{(k-1)}\land w_{kj}^{(k-1)})\] 且有\(i,j,k\le n\)

2.2. 伪代码

procedure Warshall
W:=M_R
B:=A
for k:=1 to n
    for i:=1 to n
        for j:=1 to n
        w_{ij}=w_{ij}|(w_{ik}&w_{kj})
return W

2.3. 时间复杂度

求出一项\(w_{ij}^{(k)}\)需要两次位运算，从\(W_{k-1}\)计算\(W_{k}\)需要\(2n^2\)次运算
从\(W_0\)计算出\(W_1,W_2\)一直到\(W_n\)需要\(n\)次运算
则共需\(2n^2\times n=2n^3\)次运算，时间的复杂度\(O(n^3)\)

2.4. 源码

% main function 
function W=Warshall(Mr)
% get the size of Matrix inputed
n=size(Mr);
temp=0;
W=Mr;
% init

for k=1:n
    for i=1:n
        for j=1:n             
            temp=W(i,j)|(W(i,k)&W(k,j));
            W(i,j)=temp;
        end
    end
end

3. 总结

就串行运算的话，第二种算法的时间复杂度比第一种低一个量级,算法高效
但是第一种算法可以进行并行处理，会大大提高速度

1.离散数学及其应用_第七版。ROSEN著.徐六通等译 ↩︎

1. 传递闭包的定义法1