西安电子科技大学$3.4.2关系闭包的计算-软件学院当有限集合A的基数很大时，用以上公式求A上的二元关系R的传递闭包是非常繁琐的。1960年，StephenWarshall给出了求传递闭包的一个有效算法。Warshall算法1．置新矩阵A=(MR)n×ni2. 置i=1,j-1;3．对j=1,2,..,n，如果A[i,i}=1（j=1,2,...,n），则对k=1,2,,n有A[i, k]-A[i, k]+ A[i, k];4. i=i+1;5．如果i≤n，则转步骤3，否则停止。西安电子科技大学 §3.4.2 关系闭包的计算 软件学院 当有限集合A的基数很大时，用以上公式求A上的二元关 系R的传递闭包是非常繁琐的。1960年，Stephen Warshall给出了求传递闭包的一个有效算法。 Warshall算法 1．置新矩阵A=(MR ) n ×n ； 2．置i=1, j=1； 3．对j =1, 2, ., n，如果A[j, i]=1 （j=1, 2, ., n），则 对k=1, 2, ., n 有 A[j, k]=A[j, k] ＋A[i, k]； 4．i=i+1； 5．如果 i ≤ n，则转步骤 3，否则停止