Transitive Closure of a Graph in Java

有向图的传递闭包是一个可达性矩阵，它显示了任意两个顶点之间是否存在路径。当存在从顶点 u 到顶点 v 的路径时，闭包将设置 reach[u][v] = 1；否则，reach[u][v] = 0。传递闭包被广泛应用于许多领域，包括：图论、数据库管理和查询处理以及程序分析。

问题概述

有向图是一组顶点，其中一些顶点由有向弧连接。该图的传递闭包是一个矩阵，它至少确定了两个顶点是直接相邻还是通过其他顶点相邻。

例如，在具有顶点 A、B 和 C 的图中，如果存在从 A 到 B 的路径且存在从 B 到 C 的路径，那么在传递闭包中，应该存在从 A 到 C 的路径。

Floyd-Warshall 算法

Floyd-Warshall 算法是一个所有顶点对的最短路径算法。然而，当用于传递闭包时，它可以在找到最短路径的同时，判断任意两个顶点 s 和 t 之间是否存在路径。

这是一种特殊的算法，它倾向于通过逐步生成或增强可达性矩阵。在这种情况下，对于任意两个顶点，例如“i”和“j”，我们会查看是否存在某个顶点“k”可以连接“i”和“j”。

算法步骤

• 初始化：复制图的邻接矩阵并将其放入可达性矩阵中。如果顶点 i 和 j 之间存在直接边，则设置 reach[i][j] = 1，否则设置为零。
• 更新矩阵：对于每个顶点 k，考虑所有其他顶点 i/j，并查看顶点 k 是否可以构成 i,j 之间的路径。具体来说，在以下条件下进行重要更新：如果 reach[i][k] = 1 且 reach[k][j] = 1，则令 reach[i][j] = 1。
• 结果：完成所有迭代后，(Hij) 获得了图的传递闭包的含义，该闭包由可达性矩阵给出。

文件名：TransitiveClosure.java

输出

 
Transitive closure matrix is:
1 1 1 1 
0 1 1 1 
0 0 1 1 
0 0 0 1 

解释

• 初始化：然后将 reach[][] 矩阵复制为输入邻接矩阵。
• Floyd-Warshall 算法：对于每个中间顶点 k，它会比较图中所有顶点 i 和顶点 j 是否通过顶点 K 进行连接。如果连接，则将 reach[i][j] 的值赋为 1。
• 结果：算法完成后，reach[][] 矩阵存储传递闭包，然后以矩阵形式呈现。

注意事项和边缘情况

不连通图：如果给定图中的某些顶点无法通过一个或多个顶点与其他顶点连通，则传递闭包矩阵中该顶点对的条目将保持为零。

自环：即，如果顶点 z 有一个自环，它也会反映在 graph[i][i] 中，其中 i 是其列表中的顶点编号。Floyd-Warshall 算法在这种情况下工作得非常好。

效率和性能

时间复杂度：O(V ^ 3)，其中 V 是给定图的顶点数。

空间复杂度：O(V^2)

结论

总之，可以看出传递闭包在分析有向图中顶点之间的连通性方面起着至关重要的作用。通过 Floyd-Warshall 算法，我们可以计算传递闭包并将其表示为矩阵，其中元素表示两个顶点是直接连接还是间接连接。

构建该结构所需的空间和时间限制使得该算法特别适用于所谓的“小世界”图，即顶点数量较少；O(V³) 的范围；对于大型稀疏图，还有其他更有效的方法。

由于其在数据库查询、网络、程序分析等各个领域的广泛应用，该技术是图论中的一个重要讨论话题。