传递闭包(Transitive Closure) “The transitive closure of a directed graph with n vertices can be defined as the n × n boolean matrix T = {tij }, in which the element in the i th row and the jth column is 1 if there exists a nontrivial path (i.e., directed path of a positive length) from the ith vertex to the jth vertex; otherwise, tij is 0”(Levitin, 2008).
Warshall’s algorithm aims to compute the transitive closure of a directed graph.
算法简介(Introduction) Ask a question, Is there a path from node i to node j using node k as stepping stone?
Such a path either uses node k as stepping stone or doesn’t.
We use adjacency matrix A to represent a directed graph. We can express the recurrence relation as
伪代码(Pseudocode)
function Warshall(A[1..n,1..n]) for k ⟵ 1 to n do for i ⟵ 1 to n do if A[i, k] then for j ⟵ 1 to n do if A[k, j] then A[i, j] ⟵ 1时间复杂度(Time Complexity) Time complexity of Warshall’s algorithm is Θ(n^3).
示例(Example) Here is a directed graph. Find its transitive closure. k=1. Use node 1 as stepping stone. k=2. Use node 2 as stepping stone. k=3. Use node 3 as stepping stone. k=4. Use node 4 as stepping stone. k=5. Use node 5 as stepping stone. k=6. Use node 6 as stepping stone. k=7. Use node 7 as stepping stone. Hence, the transitive closure is,
Java Code’
java code运行结果(Result)
result写在最后的话(PS) Welcome questions always and forever.
