【概述】

傳遞閉包：對于一個節(jié)點 i，如果 j 能到 i，i 能到 k，那么 j 就能到 k，求傳遞閉包，就是把圖中所有滿足這樣傳遞性的節(jié)點計算出來，計算完成后，就知道任意兩個節(jié)點之間是否相連。

簡單來說，傳遞閉包是一種關于連通性的算法，其是指所有點的所能到達的點集。

【傳遞閉包的計算】

Floyd 可以用來判斷圖中兩點是否連通，在求連通性的同時，可以進行傳遞閉包計算。

對于一個沒有邊權的圖，可將相鄰兩點距離設為 dis[i][j]=true，不相鄰的兩點距離設為 dis[i][j]=false，而后進行 Floyd 算法即可。?

for(int k=1;k<=n;k++)//第一重循環(huán)為i→j的中間點kfor(int i=1;i<=n;i++)//第二重循環(huán)為起點ifor(int j=1;j<=n;j++)//第三重循環(huán)為終點jif(dis[i][j]>dis[i][k]+dis[k][j])//如果i→k的距離加上k→j的距離小于i→j的距離if(dis[i][k]&&dis[k][j])//更新最短路徑dis[i][j]=true;

總結

以上是生活随笔為你收集整理的图论 —— 图的连通性 —— 传递闭包的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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