算法思想
如右圖
算法介紹
1、引言
Warshall在1962年提出了一個求關係的傳遞閉包的有效算法。其具體過程如下,設在n個元素的有限集上關係R的關係矩陣為M:
(1)置新矩陣A=M;
(2)置k=1;
(3)對所有i如果A[i,k]=1,則對j=1..n執行:
A[i,j]←A[i,j]∨A[k,j];
(4)k增1;
(5)如果k≤n,則轉到步驟(3),否則停止。
所得的矩陣A即為關係R的傳遞閉包t(R)的關係矩陣。
在左孝凌等編著的《離散數學》中提到了該算法,但並未對此算法作出解釋。下面本文將對該算法的思想作出一種比較通俗的解說。
2、對Warshall算法的解說
設關係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算法求關係的傳遞閉包繞了彎子。
參考文獻:
[1]左孝凌,李為鑑,劉永才,《離散數學》,上海:上海科學技術文獻出版社,1982
[2]嚴蔚敏,吳偉民,《數據結構 C語言版》,北京:清華大學出版社,1997