沃舍尔算法.ppt

文档介绍：考虑n+1个矩阵的序列M0, M1, …, Mn.
Mk[i,j]=1当且仅当在R关系图中存在一条从xi到xj的路径, 并且这条路径除端点外中间只经过{ x1, x2, ..., xk }中的结点.
不难证明M0是R的关系矩阵, 而Mn就对应R的传递包.
沃舍尔算法从M0开始, 顺序计算M1, M2, …直到Mn为止.
假设已有Mk, 如何计算Mk+1?
Mk+1[i, j] = 1当且仅当在R的关系图中存在一条xi到xj, 并且中间只经过{ x1, x2, …, xk, xk+1 }的路径.
这时可路径分成两种情况:
Mk[i, j] = 1;
Mk[i, k+1] = 1 且 Mk[k+1, j] = 1
Warshall 算法
整理ppt
Warshall 算法
输入：M（R的关系矩阵）
输出：MT（t(R)的关系矩阵）
←M
k ← 1 to n do
3. for i ← 1 to n do
4. for j ← 1 to n do
5. MT[i,j]←MT[i,j]+MT[i,k]*MT[k,j]
注意：算法中矩阵加法和乘法中的元素相加都使用逻辑加。
整理ppt
Warshall 算法 举例
例 设A={a,b,c,d}，R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>}， 求t(R)。
分析 k＝1 时，MT[i,j]←MT[i,j]+MT[i,1]*MT[1,j]
MT[1,j]←MT[1,j]+MT[1,1]*MT[1,j]
MT[2,j]←MT[2,j]+MT[2,1]*MT[1,j] 将第1行加到第2行上
MT[3,j]←MT[3,j]+MT[3,1]*MT[1,j]
MT[4,j]←MT