传递闭包

什么叫传递闭包

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

给定一个有向图$G$，那么“传递闭包”就是指“图上一点$i$能否到达另一点$j$”。

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

$\text{Floyd}$求传递闭包

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

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

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

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;
}

$\text{Floyd}$判环

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

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

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;
}

本文永久链接是：https://sweetlemon39.github.io/transitive-closure/