1、1,34 传递闭包及WARSHALL算法,2,设S是一个含有n个元素 a1，a2，an 的集合。S上的二元关系A是笛卡儿积SS的子集。如(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有一
2、条边。这样的矩阵称为图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的乘方 M2MM 也是n阶方矩
3、阵，其元素定义为 n M2ijMisMsj s=1其中的乘法、加法分别是逻辑乘(AND)，逻辑加(OR)显而易见M2ij为T，则从节点i到节点j有一条长度为2的路径。,7,同样可以定义关系矩阵的幂 MkMk-1M (K1)其元素 n MkijMk-1isMsj s=1显而易见Mkij为T，则从节点i到节点j有一条长度为k的路径。因此若(i，j) A*，则存在K=n一1),9,为计算传递闭包矩阵只须计算M矩阵的n一1次幂Mn-1即可。如已知关系矩阵M，计算传递闭包矩阵M*的方法为：将矩阵M连续平方 log 2 (n一1)次。矩阵平方运算的时间复杂度为0(n3)，从而计算M*的时间复杂度为0(n3
4、 log(n-1)下面给出的WARSHALL算法的输出也是传递闭包矩阵，其复杂度为O(n3)。,10,void WARSHALL 输入:M，关系R的关系矩阵 输出:M*，R的传递闭包矩阵 for (i=1; i n; i+ ) for (j1; j n; j+ ) if(M j，iT) for (k=1; i=1) (6) 且 (J， el) R (es ， es+1) R (s=1，2， ，p-1) (ep ，K) R 令 eqmax(el，e2， ，ep),18,对eq的值进行归纳。如eq1，则(6)中的序列只含有一个数值：1，则 (j，1) R (1，K) R 则当i1 eq ，的循环开
5、始执行时，有 MJ，1M1，KT 由(5)可知 MJ，K 的值在这次循环结束时变为T，且不再改变。,19,设eq值为1，2，i-1，在eq次循环结束时，MJ，K的值为T (*) 令eqi，考虑(6)的两个子序列 el，e2， ，eq-l (7) 和 eq+l， ，ep， (8) 设这两个子序列不空，则 emax(el，e2， ，eq-l )eq i emax(eq+l， ，ep) eq i,20,(*)的含意是: (J，K) R*, 只要 el，e2， ，ep，中的最大值et为1，2，i-1中的一个, 则当I=et次循环结束时候, MJ，K为T.(J，i) 和(i，K) 都满足假设的条件.(i=eq)因为(7)(8)都满足条件. 序列(7)的前驱和后继分别是j和eq(=i),21,由上述归纳假设，在I次循环开始执行之前有 MJ，IT同样的理由, Mi，KT ( 须注意，现在eqi，)按式(5)在I次循环后MJ，K的值变成T,22,如子序列(7)，(8)为空，则更容易证明，我们只须指出子序列(7)为空，表示eq 是序列(6)的第一个元素；子序列(8)为空，表示eq是序列(6)的最后一个元素，则 (J，eq) R 或 (eq，K) R 此即M J，eq或Meq，K的值在算法一开始时就是T，所以M J，K在li的循环中必定变为T这就证明了 R* ( A 证毕。,
