图论 —— 图的连通性 —— 传递闭包

  • Post author:
  • Post category:其他


【概述】


传递闭包

:对于一个节点 i,如果 j 能到 i,i 能到 k,那么 j 就能到 k,求传递闭包,就是把图中所有满足这样传递性的节点计算出来,计算完成后,就知道任意两个节点之间是否相连。

简单来说,传递闭包是一种关于连通性的算法,其是指所有点的所能到达的点集。

【传递闭包的计算】

Floyd 可以用来判断图中两点是否连通,在求连通性的同时,可以进行传递闭包计算。

对于一个没有边权的图,可将相邻两点距离设为 dis[i][j]=true,不相邻的两点距离设为 dis[i][j]=false,而后进行 Floyd 算法即可。

for(int k=1;k<=n;k++)//第一重循环为i→j的中间点k
    for(int i=1;i<=n;i++)//第二重循环为起点i
        for(int j=1;j<=n;j++)//第三重循环为终点j
            if(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;



版权声明:本文为u011815404原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。