关系的闭包,warshall算法

作者: Rememberautumn 分类: 未分类 发布时间: 2014-10-14 15:38 阅读: 2,583

大一一年参加过acm的培训,也学过一些算法和数据结构,但是觉得自己一直没搞明白算法的魅力与精髓,这次离散数学课也是收获不少。

设关系R的关系图为G,设图G的所有顶点为v1,v2,…,vn,则t(R)的关系图可用该方法得到:若G中任意两顶点vi和vj之间有一条路径且没有vi到vj的弧,则在图G中增加一条从vi到vj的弧,将这样改造后的图记为G’,则G’即为t(R)的关系图。G’的邻接矩阵A应满足:若图G中存在从vi到vj路径,即vi与vj连通,则A[i,j]=1,否则A[i,j]=0。
这样,求t(R)的问题就变为求图G中每一对顶点间是否连通的问题。
定义一个n阶方阵序列A(0),A(1),A(2),…,A(n),每个方阵中的元素值只能取0或1。A(m)[i,j]=1表示存在从vi到vj且中间顶点序号不大于m的路径(m=1..n),A(m)[i,j]=0表示不存在这样的路径。而A(0)[i,j]=1表示存在从vi到vj的弧,A(0)[i,j]=0表示不存在从vi到vj的弧。
这样,A(n)[i,j]=1表示vi与vj连通,A(n)[i,j]=0表示vi与vj不连通。故A(n)即为t(R)的关系矩阵。
那么应如何计算方阵序列A(0),A(1),A(2),…,A(n)呢?
很显然,A(0)=M(M为R的关系矩阵)。
若A(0)[i,1]=1且A(0)[1,j]=1,或A(0)[i,j]=1,当且仅当存在从vi到vj且中间顶点序号不大于1的路径,此时应将A(1)[i,j]置为1,否则置为0。
一般地,若A(k-1)[i,k]=1且A(k-1)[k,j]=1,或A(k-1)[i,j]=1,当且仅当存在从vi到vj且中间顶点序号不大于k的路径,此时应将A(k)[i,j]置为1,否则置为0(k=1..n)。用公式表示即为:
A (k)[i,j]=(A(k-1)[i,k]∧A(k-1)[k,j])∨A(k-1)[i,j] i,j,k=1..n
这样,就可得计算A(k)的方法:先将A(k)赋为A(k-1);再对所有i=1..n,若A(k)[i,k]=1(即A(k-1)[i,k]=1),则对所有j=1..n,执行:
A (k)[i,j]←A(k)[i,j]∨A(k-1)[k,j]
但这与前述Warshall算法中的第(3)步还有一定距离。若将上式改为:
A(k)[i,j]←A(k)[i,j]∨A(k)[k,j] (即把A(k-1)[k,j]改为A(k)[k,j])
就可将上标k去掉,式子就可进一步变为:
A[i,j]←A[i,j]∨A[k,j]
这样可以只用存储一个n阶方阵的空间完成计算,且与前述Warshall算法中第(3)步的式子一致。那么,可不可以把A(k-1)[k,j]改为A(k)[k,j]呢?答案是肯定的。下面将证明在计算A(k)的过程中A(k-1)[k,j]与A(k)[k,j]相等(A(k)被赋初值A(k-1)后)。考察计算A(k)的方法 只有当i=k时A(k)[k,j]的值才有可能改变,此时将式A(k)[i,j]←A(k)[i,j]∨A(k-1)[k,j]中的i换为k,得A(k)[k,j]←A(k)[k,j]∨A(k-1)[k,j],对某一j,执行该式的赋值操作前A(k)[k,j]=A(k-1)[k,j],因为计算A(k)开始时A(k)被赋为A(k-1),故它们相或的结果等于A(k-1)[k,j],故赋值操作不改变A(k)[k,j]的值。这样,就没有操作会改变A(k)[k,j]的值,故A(k-1)[k,j]与A(k)[k,j]相等。
综上,就可得到计算A(n)的算法,且该算法与前述的Warshall算法完全一致。
由上面的分析,不难看出,Warshall算法类似于求图中每对顶点间最短路径的Floyd算法。其实,用Floyd算法也能求关系的传递闭包,方法为令关系R的关系图G中的每条弧的权值都为1,这样得一有向网G1,设G1的邻接矩阵为D(-1)(若vi无自回路,则D(-1)(i,i)=∞),对G1用Floyd算法求其每对顶点间最短路径,得结果矩阵D(n-1)。因若G中vi与vj连通,当且仅当D(n-1)[i,j]≠∞,故将矩阵D中的∞都改为0,其它值都改为1,得矩阵A,则矩阵A即为t(R)的关系矩阵。Floyd算法和Warshall算法的时间复杂度都为O(n3),但明显用Floyd算法求关系的传递闭包绕了弯子。

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

发表评论

电子邮件地址不会被公开。 必填项已用*标注