§3．4 传递闭包及WARSHALL算法.

Presentation on theme: "§3．4 传递闭包及WARSHALL算法."— Presentation transcript:

1 §3．4 传递闭包及WARSHALL算法

2 设S是一个含有n个元素 a1，a2，…，an 的集合。S上的二元关系A是笛卡儿积S×S的子集。 如(ai,aj) ∈ A，则ai与aj有A关系。 关系A可用n阶方矩阵M表示，矩阵M的第i行，第j列元素Mij定义为 1 (TRUE), 如果(ai,aj) ∈ A 0 (FALSE), else 称M为关系矩阵

3 图G是有序对(V，E)，其中非空集合V是图G的节点集合，E是图的边集合。
图G的邻接关系A定义为：如从节点i到节点j有一条边，则 (i，j) ∈ A 否则 (i, j) !∈ A 显然关系A可用方矩阵M表示，其阶数为图的节点数|V|， Mij为T当且仅当节点i到节点j有一条边。 这样的矩阵称为图G的邻接矩阵。

4 设R是一个关系，其传递闭包R’也是关系，定义为： (ai,aj) ∈ R’当且仅当存在序列
ak1,ak2,…,akp ， 且 ak1= ai ， akp= aj ， (aks,aks+1 ) ∈ R (s=l，2 ,…, p-1) 相应于传递闭包的关系矩阵称为传递闭包矩阵。

5 图G＝(V，E)的邻接关系A的传递闭包A*的含意为，
若(i, j ) ∈ A*，则有一条从节点i到节点j的路径， 因而邻接关系的传递闭包也称为图的连通关系， 相应的矩阵M*称为G的连通矩阵。 矩阵M及矩阵M*的元素都是逻辑值真(T)或假(F)， 所以M和M*都是逻辑矩阵。

6 矩阵M的乘方 M2＝M×M 也是n阶方矩阵，其元素定义为 n M2ij＝∑Mis×Msj s=1 其中的乘法、加法分别是逻辑乘(AND)，逻辑加(OR)．显而易见M2ij为T，则从节点i到 节点j有一条长度为2的路径。

7 显而易见Mkij为T，则从节点i到节点j有一条长度为k的路径。 因此若(i，j) ∈A*，则存在K<n使得 Mkij ＝T 从而
同样可以定义关系矩阵的幂 Mk＝Mk-1×M (K>1) 其元素 n Mkij＝∑Mk-1is×Msj s=1 显而易见Mkij为T，则从节点i到节点j有一条长度为k的路径。 因此若(i，j) ∈A*，则存在K<n使得 Mkij ＝T 从而 n-1 M*＝M+M2+ · · · +Mn-1＝∑Mk

8 其中加法是逻辑加(OR)． 如果认为每个节点与其本身邻接，即 (i，i) ∈ A 则Mij ＝T表示从节点i到节点j有一条边或i＝j，此即从i到j有一条长度不超过1的路径， M2ij＝T则表示从i到j有一条长度不大于2的路径，同样地，Mkij＝T表示从i到j有一条长度不大于k的路径，因此有 M*=Mn-1 · M*＝Mk · (k>=n一1)

9 为计算传递闭包矩阵只须计算M矩阵的n一1次幂Mn-1即可。如已知关系矩阵M，
计算传递闭包矩阵M*的方法为：将矩阵M连续平方 log 2 (n一1)次。 矩阵平方运算的时间复杂度为0(n3)，从而计算M*的时间复杂度为0(n3 log(n-1))． 下面给出的WARSHALL算法的输出也是传递闭包矩阵，其复杂度为O(n3)。

10 void WARSHALL 输入:M，关系R的关系矩阵 输出:M*，R的传递闭包矩阵 for (i=1; i<＝ n; i++ ) for (j＝1; j<＝ n; j++ ) if(M [j，i]＝T) for (k=1; i<＝ n; i++ ) m [j，k] + ＝m [i，k]; (4) 上述算法必定会在有限时间内结束运行。 整个算法是三重嵌套的循环语句， 易知WARSHALL算法的时间复杂度为O(n3)。

11 在证明算法的正确性之前, 先看一下算法是如何运行的.
当i和j固定时, 内层for循环一次就是把m矩阵的第j行的元素从左到右地更新一遍. 当i固定时, 中间层for循环一次, 就是把m矩阵的所有行从上到下地更新一遍. 因此, 整个算法就是把m矩阵的所有元素更新n遍.

12 定理 WARSHALL算法的输出矩阵是输入关系矩阵的传递闭包矩阵。
证 注意到算法的输入、输出矩阵都存储在M中，与M相应的关系用A表示。 输入关系用R表示，其传递闭包用R*表示。则须证在算法运行结束时 1. A （ R* 2. R* （ A 定理的证明分成相应的两部分。

13 1. 欲证算法运行结束时A （ R*，只须证在算法的每次循环后, A（ R*成立。此即要证：
如果 (J，K) ∈ A，则(J，K) ∈ R* 对算法的循环控制变量i，使用归纳法。在算法开始时，显然有 A＝R ∈ R* 将(4)等价地改写为(因为M [j，i]＝T) M[J，K] +＝ M [j，i] × M[i，K] (5) 考虑i值为1时的循环结束时，从(5)可知，M[J，K]值为T(就是(J，K) ∈ A)有两种情况：

14 a. M[J，K]在循环之前为T,即 (J，K) ∈ R，则(J，K) ∈ R* b. M [J，I]＝M [i，K]＝T，则
M[J，K] +＝ M [j，i] × M[i，K] (5) a. M[J，K]在循环之前为T,即 (J，K) ∈ R，则(J，K) ∈ R* b. M [J，I]＝M [i，K]＝T，则 (J，i) ∈ R， (i，K) ∈ R 这蕴含着 (J，K) ∈ R*

15 假设i值为l，2, · · · , I-1的各次循环结束时，
如果M[J，K] =T 则 (J，K) ∈ R* 循环控制变量为I，相应的循环结束时M [J，K]＝T，同样要考虑两种情况 a．M [J，K]值在I-1的循环结束时就是T，按归纳假设 b．在I-1循环结束时有 M[J，i]＝M[i，K]＝T 此即 (J，i) ∈ R*，(i，K) ∈ R* 这蕴含着 这样，我们就证明了A ( R*

16 2．欲证运行结束时 R* ( A 也就是要证，如(J，K) ∈ R*，则M [J，K]最终必为T．分两种情况:

17 ① (J，K) ∈ R，则算法开始运行时M[J，K]值为T，由(5)可知在算法运行过
②(J，K)!∈ R, 但(J，K) ∈ R*，则必存在有限序列 el，e2，· · · ，ep， (p>=1) (6) 且 (J， el) ∈ R (es ， es+1) ∈ R (s=1，2， · · · ，p-1) (ep ，K) ∈ R 令 eq＝max(el，e2， · · · ，ep)

18 对eq的值进行归纳。 如eq＝1，则(6)中的序列只含有一个数值：1，则 (j，1) ∈ R (1，K) ∈ R 则当i＝1＝ eq ，的循环开始执行时，有 M[J，1]＝M[1，K]＝T 由(5)可知 M[J，K] 的值在这次循环结束时变为T，且不再改变。

19 设eq值为1，2，…，i-1，在eq次循环结束时，M[J，K]的值为T． (*)
el，e2，· · ·，eq-l (7) 和 eq+l， · · · ，ep， (8) 设这两个子序列不空，则 e’＝max(el，e2，· · ·，eq-l )<eq ＝ i e’’＝max(eq+l， · · · ，ep) < eq ＝ i

20 (*)的含意是: (J，K) ∈ R*, 只要 el，e2，· · · ，ep， 中的最大值et为 1，2，…，i-1 中的一个, 则当I=et次循环结束时候, M[J，K]为T. (J，i) 和(i，K) 都满足假设的条件.(i=eq) 因为(7)(8)都满足条件. 序列(7)的前驱和后继分别是j和eq(=i)

21 由上述归纳假设，在I次循环开始执行之前有
M[J，I]＝T 同样的理由, M[i，K]＝T ( 须注意，现在eq＝i，)按式(5)在I次循环后M[J，K]的值变成T．

22 如子序列(7)，(8)为空，则更容易证明，我们只须指出子序列(7)为空，表示eq
(J，eq) ∈ R 或 (eq，K) ∈ R 此即M [J，eq]或M[eq，K]的值在算法一开始时就是T，所以M [J，K]在l＝i的循环中必定变为T．这就证明了 R* ( A 证毕。