1.離散數(shù)學(xué)定義：

t(R) = R u R^2 u R^3 u..... 其中R^(n+1) = R^n 復(fù)合 R

矩陣表示：

M（R） = M + M^2 + M^3 +....+M^n(其中加為邏輯加）

所以我們只要按照這個(gè)公式每次更新M，最后的Mn就是傳遞閉包

?

2.Warshall算法：

(1)置新矩陣A＝M；?

(2)i＝1；?

(3)對所有j如果A[j，i]＝1，則對k＝1，2，…，n，A[j，k]＝A[j，k]∨A[i，k]；?
(4)i加1；（i是行，j是列）?

?

(5)如果i≤n，則轉(zhuǎn)到步驟3)，否則停止。?

?

思想：不難理解,對于每個(gè)相通的j - > i,我們可以從這個(gè)相通關(guān)系出發(fā)，看看能不能通過這條相通的j - > i,更新一下j - >k。對所有的可通關(guān)系都更新一遍M，最后的結(jié)果就是傳遞閉包了！

代碼：

#include <iostream> #include<cstring> using namespace std; const int maxn = 100; int G[maxn][maxn];//離散數(shù)學(xué)定義法 int main() {int T;cin>>T;while(T--){memset(G,0,sizeof(G));int n,m;cin>>n>>m;//n個(gè)點(diǎn)m條邊f(xié)or(int i = 1;i<=m;i++){int a,b;cin>>a>>b;G[a][b] = 1;//建邊}for(int i =1;i<=n;i++){//外層枚舉到達(dá)點(diǎn)for(int j = 1;j<=n;j++){//內(nèi)層枚舉出發(fā)點(diǎn)if(G[j][i]){//如果j - >i相通for(int k = 1;k<=n;k++){//從這條通路出發(fā)，更新所有的傳遞關(guān)系G[j][k] = G[j][k]|G[i][k];（若G[j][k] = 0,但G[j][k] = G[j][i] 復(fù)合 G[i][k])}}}}for(int i = 1;i<=n;i++){for(int j = 1;j<=n;j++){cout<<G[i][j]<<" ";}cout<<endl;}}return 0; }

3.在動(dòng)態(tài)規(guī)劃思想上實(shí)現(xiàn)沃舍爾算法

(1)這個(gè)算法類似于最短路的floyd算法，可以說floyd是在更新傳遞閉包的基礎(chǔ)上記錄生成傳遞閉包的最小代價(jià)，這個(gè)最小代價(jià)就是最短路，所以說，最短路和沃舍爾求傳遞閉包的思想是一樣的或者是相通的！神奇！

代碼：

#include <iostream> #include<cstring> using namespace std; const int maxn = 100; int G[maxn][maxn]; int main() {int T;cin>>T;while(T--){memset(G,0,sizeof(G));int n,m;cin>>n>>m;for(int i = 1;i<=m;i++){int a,b;cin>>a>>b;G[a][b] = 1;}for(int k = 1;k<=n;k++){//經(jīng)過節(jié)點(diǎn)k中轉(zhuǎn)，能更新多少傳遞關(guān)系for(int i = 1;i<=n;i++){for(int j = 1;j<=n;j++){if(G[i][j])continue;G[i][j] = (G[i][k]&&G[k][j]);}}}for(int i = 1;i<=n;i++){for(int j = 1;j<=n;j++){cout<<G[i][j]<<" ";}cout<<endl;}}return 0; }

4.POj 3660?Cow Contest

（1）題意：有n頭牛互相比賽，現(xiàn)在給出m種已知的比賽結(jié)果。注：若A打敗B，B打敗C，則A可以打敗C。問你根據(jù)這個(gè)表最終能確定幾頭牛的排名。

（2）分析：能確定排名的肯定是和其他所有的牛的關(guān)系間接或者直接的知道了，所以這里等價(jià)于求關(guān)系的傳遞閉包，某頭牛的所有入度和出度之和等于n - 1時(shí)表示這頭牛和其他所有牛的關(guān)系都有了那么這頭牛的排名肯定就確定了。

（3）代碼：

?#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 100+5; int G[maxn][maxn]; int main() {int n,m;memset(G,0,sizeof(G));scanf("%d%d",&n,&m);for(int i = 0;i<m;i++){int a,b;scanf("%d%d",&a,&b);G[a][b] = 1;}for(int k = 1;k<=n;k++){//求傳遞閉包for(int i = 1;i<=n;i++){for(int j = 1;j<=n;j++){if(i==j||G[i][j])continue;else if(G[i][k] == 1&&G[k][j]==1)G[i][j] ?= 1;}}}int ans = 0;//統(tǒng)計(jì)總的可確定排名牛的數(shù)目for(int i = 1;i<=n;i++){int sum = 0;//統(tǒng)計(jì)編號i牛的度數(shù)和for(int j = 1;j<=n;j++){if(i==j)contiue;if(G[i][j]||G[j][i])sum++;}if(sum==n-1)ans++;}printf("%d\n",ans);return 0; }

?

————————————————
原文鏈接：https://blog.csdn.net/qq_40772692/article/details/80351390

總結(jié)

以上是生活随笔為你收集整理的使用 Warshall（沃舍尔）算法求解关系的传递闭包的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。