1、傳遞閉包的計算,(Warshall算法),傳遞閉包的計算(Warshall算法),設(shè)關(guān)系R的傳遞閉包為t(R)，其矩陣表示為Mt。 輸入：M 輸出： Mt (1) 用關(guān)系矩陣M表示關(guān)系R (2) 置變量j = 1 (3) 對于所有i，如果mij = 1, 對可k = 1, 2, , n, 置 mik = mik + mjk(布爾加） 即：將第i行與第j行相加，所得結(jié)果寫回第i行。 (4) j = j + 1; (5) 如果jn, 轉(zhuǎn)至步驟(3), 否則停止。,RM，j=1,結(jié) 束,開始,mij = 1,mik = mik + mjk,+j = n,Y,N,Y,N,Warshall算法應(yīng)用舉例,

2、例：設(shè)關(guān)系R的關(guān)系矩陣表示如下圖M所示，求它的傳遞閉包。,M,AM，j=1,結(jié) 束,開始,mij = 1,mik = mik + mjk,+j = n,Y,N,Y,N,Warshall算法應(yīng)用舉例(續(xù)),j = 1 m21 = 1，i = 2; 第i行：1 0 1 0 第j行：0 1 0 0 + 1 1 1 0 相加之后寫回第i行：,M,AM，j=1,結(jié) 束,開始,m21 = 1,m2k = m2k + m1k,+j = n,Y,N,Y,N,mij,1,布爾加：00 = 0 01 = 1 1+0 = 1 10 = 1 1+1 = 1,Warshall算法應(yīng)用舉例(續(xù)),j = j + 1 n

3、= 4 j = 1 + 1 = 2 j = n,M,AM，j=1,結(jié) 束,開始,m21 = 1,m2k = m2k + m1k,+j = n,Y,N,Y,N,mij,1,Warshall算法應(yīng)用舉例(續(xù)),j = 2 m12 = 1; i = 1 第i行：0 1 0 0 第j行：1 1 1 0 + 1 1 1 0 相加之后寫入第i行：,M,AM，j=1,結(jié) 束,開始,m12 = 1,m1k = m1k + m2k,+j = n,Y,N,Y,N,mij,1,1,1,注意：第j行中存在m22 = 1, 仍然需要再作一次加法。,Warshall算法應(yīng)用舉例(續(xù)),j = j + 1 n = 4 j = 2+1 =3 j = n,M,AM，j=1,結(jié) 束,開始,m22 = 1,m2k = m2k + m2k,+j = n,Y,N,Y,N,mij,1,1,1,Warshall算法應(yīng)用舉例(續(xù)),M,1,1,1,訪問m22之后，將依次訪問: 第3列：m13, m23 第4列：m14, m24, m34,mij,1,1,AM，j=1,結(jié) 束,開始,mij = 1,mik = mik + mjk,+j = n,Y,N,Y,N,j = 4 +j= n不成立，程序運(yùn)