Transitive Closure of a Graph Using Floyd-Warshall Algorithm in Java

在图论中，有向图的传递闭包是指顶点的可达性。传递闭包可以帮助我们确定网络中两个顶点之间是否存在路径。

Floyd-Warshall 算法是计算图的传递闭包的一种常用方法。除了通常用于加权图中的最短路径计算外，动态规划技术还可以修改用于解决传递闭包问题。正如本文将要看到的，这种方法可用于计算有向图的传递闭包。

问题陈述

给定一个具有 V 个顶点的有向图，我们的任务是确定每个顶点是否可以从其他所有顶点到达。传递闭包可以用一个 V x V 的矩阵表示，其中

• closure[i][j] = 1，如果存在从顶点 i 到顶点 j 的路径，
• 否则，closure[i][j] = 0。

使用 Floyd-Warshall 算法计算传递闭包

确定顶点 k 是否可以充当顶点 i 和 j 之间的桥梁。该矩阵最初配置为，如果存在从 i 到 j 的边（包括 i == j），则 closure[i][j] = 1，否则为 0。随后，算法会遍历每个潜在的中间顶点，确定是否可以通过建立中间顶点来形成间接路径。

算法

构建一个 V x V 的二维矩阵 closure[][]。使用图的邻接矩阵来初始化此矩阵。如果 i 和 j 之间存在边，则将 closure[i][j] 设置为 1。如果不存在，则设置为零。另外，由于一个顶点始终可以到达自身，因此对于所有 i，都将 closure[i][i] 设置为 1。

1. 更新 closure 矩阵，对于每个充当中间顶点的顶点 k。检查是否存在一条从 i 到 j 且经过 k 的路径。为此，请确保 closure[i][k] 和 closure[k][j] 都等于 1。如果这两个条件都满足，则将 closure[i][j] 设置为 1。
2. 处理完所有顶点后，closure[][] 矩阵将表示图的传递闭包。

文件名：TransitiveClosure.java

输出

 
Transitive closure of the given graph:
1 1 1 1 
0 1 1 1 
0 0 1 1 
0 0 0 1   

解释

首先，在Java 代码中，使用Floyd-Warshall 算法为传递闭包初始化一个二维矩阵 closure[][]，以存储从输入邻接矩阵复制的可达性信息。

对于每个条目，如果顶点 i 和 j 之间存在直接边，则 closure[i][j] 的初始值设置为 1，否则为 0。然后，该算法使用三个嵌套循环。

内部两个循环遍历所有顶点对 (i, j)，以确定是否存在从 i 到 j 且经过 k 的路径，而外部循环遍历所有顶点 k，充当中间顶点。

如果 i 可以到达 k，并且 k 可以到达 j，则它会将 closure[i][j] 更改为 1，表示它们之间存在路径。最后，打印传递闭包矩阵，显示哪些顶点可以从其他顶点到达。

复杂度

• 由于所有 V 个顶点都通过三个循环进行排序，因此 Floyd-Warshall 算法的时间复杂度为 O(V^3)。
• 传递闭包矩阵的空间复杂度为 O(V^2)。

结论

Floyd-Warshall 算法是一种用于计算有向图传递闭包解决方案的协议。它通常应用于加权网络中的最短路径，但由于其系统搜索任意两个顶点之间所有路径的能力，因此非常适合传递闭包问题。此方法还通过保证可达性矩阵的覆盖率，成为图论中有用的辅助工具。