传递闭包的算法及应用.doc

信阳师范学院学报(自然科学版)
第 12 卷第 3 期 1999 年 7 月
Jou rna l of X inyang T each e r s Co llege
(N a tu ra l Science E d it ion)V o l. 12 N o. 3 J u l. 1999
传递闭包的算法及应用
α
侯云山1 , 许中华2 , 刘宏兵1
(1. 信阳师范学院计算机系, 河南信阳 464000; 2. 淮阳师范学校, 河南淮阳 466700)
摘要: 传递闭包是一种重要的关系运算。它在数据结构、编译理论和关系数据库中都有广泛
的应用。本文详细地探讨关系的传递闭包的概念、算法和应用。
关键词: 传递闭包; W A R SHA LL 算法; 语法分析 SQ L
中图分类号: O 157. 4; T P 311. 12 文献标识码: A 文章编号: 100320972 (1999) 0320347203
关系的运算包括关系的合成、关系的逆以及关系
的闭包运算等, 而在自反闭包、对称闭包和传递闭包三种运算中尤以传递闭包最为复杂和重要, 由于一般的教材只涉及到它的某个方面, 故难以令人对关系闭包有一个比较完整和系统的认识。本文正是以此为出发点, 力求给读者一个清晰全面的概念。
定义
设 R 为 A
上的二元关系, 如果有另一个
二元关系 R ′满足: a) R ′是传递的; b) 对任何传递的关
系 R ″, 如果有 R ″Β R , 就有 R ″Β R ′, 则称关系 R ′为 R
的传递闭包, 记作 t (R ).
一个传递关系 R 的传递闭包是 R 本身。
2 W a rsha ll 算法
求一个关系的传递闭包方法主要包括深度优先搜索、W a r sh a ll 算法和二进位矩阵相乘法, 所有这些算法在最坏情况下的时间复杂度为 o (n3 ) , 它们做不同类型运算, 不同运算次数和不同形式输入数据工作。我们这里主要讨论W a r sh a ll 算法 1
如果 A 上二元关系 R 用关系图表示, 则寻找关系 R 的传递闭包 t (R ) 的元素相当于在有向图中插入
1 二元关系的传递闭包
设A 是一个含有元素 x 1 , x 2 , , x n 的有限集, 则 A 上的二元关系 R 是笛卡尔积 A ×A 的一个子集, R 中的任一序偶可写为< x i, x j > ∈R 或 x iR x j。
关系可以用关系矩阵或关系图表示, 如果用关系矩阵, 则关系 R 的关系矩阵M R 为
M R = rij ]n×n , i, j = 1, 2,
1, 若< x i , x j > ∈R
, n,
边。特别是, 对已插入的一对边x ix k 和x k x j , 我们加进
rij =
0, 反之
边x ix j。这就是说, 如果我们已知对某个 k 有 x iR x k 和
x kR x j , 则能得出结论 x iR x j。
记M R 为 R 的关系矩阵,M t (R ) 为 R 的传递闭包
t (R ) 的关系矩阵, 则不难利用下述算法可以求出
t (R )。
11M t (R ) ←M R
2. fo r k = 1 to n
3. fo r i= 1 to n
如