什么叫传递闭包

“传递闭包”这个名字听起来很吓人,其实它不难理解。

给定一个有向图GG,那么“传递闭包”就是指“图上一点ii能否到达另一点jj”。

“传递”二字概括了“传递闭包”的意义:描述具有传递性的性质,比如小于关系具有传递性、两非零向量平行(或线性相关)具有传递性,等等。

Floyd\text{Floyd}求传递闭包

Floyd\text{Floyd}是极其著名的最短路算法。既然是最短路算法,那就也可以用来求传递闭包。

使用时要把图存在邻接矩阵里。另外要注意循环顺序是k,i,jk,i,j

时间复杂度O(n3)\text{O}(n^3)

1
2
3
4
5
6
7
void floyd(void){
for (int k=1;k<=n;k++)
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (g[i][k] && g[k][j])
g[i][j]=1;
}

Floyd\text{Floyd}判环

这是很懒的一种做法,只需求一遍传递闭包,然后看一看有没有自环既可。

时间复杂度O(n3)\text{O}(n^3)。(当然,用dfs\text{dfs}可以O(n+m)\text{O}(n+m),只不过码量稍稍大一点。)

1
2
3
4
5
6
7
8
9
10
11
12
bool floyd(void){
//Return 1 if circles exist.
for (int k=1;k<=n;k++)
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (g[i][k] && g[k][j])
g[i][j]=1;
for (int i=1;i<=n;i++)
if (g[i][i])
return 1;
return 0;
}

评论