Warshall’s Algorithm -to find TRANSITIVE CLOSURE
Warshall’s Algorithm
-to find TRANSITIVE CLOSURE
Some useful definitions:
• Directed Graph: A graph whose every edge is directed is called directed graph OR digraph
• Adjacency matrix: The adjacency matrix A = {aij} of a directed graph is the boolean matrix that has
o 1 - if there is a directed edge from ith vertex to the jth vertex
o 0 - Otherwise
• Transitive Closure: Transitive closure of a directed graph with n vertices can be defined as the n-by-n matrix T={tij}, in which the elements in the ith row (1≤ i ≤ n) and the jth column(1≤ j ≤ n) is 1 if there exists a nontrivial directed path (i.e., a directed path of a positive length) from the ith vertex to the jth vertex, otherwise tij is 0.
The transitive closure provides reach ability information about a digraph.
Computing Transitive Closure:
• We can perform DFS/BFS starting at each vertex
• Performs traversal starting at the ith vertex.
• Gives information about the vertices reachable from the ith vertex
• Drawback: This method traverses the same graph several times.
• Efficiency : (O(n(n+m))
• Alternatively, we can use dynamic programming: the Warshall’s Algorithm
Underlying idea of Warshall’s algorithm:
• Let A denote the initial boolean matrix.
• The element r(k) [ i, j] in ith row and jth column of matrix Rk (k = 0, 1, …, n) is equal to 1 if and only if there exists a directed path from ith vertex to jth vertex with intermediate vertex if any, numbered not higher than k
• Recursive Definition:
• Case 1:
A path from vi to vj restricted to using only vertices from {v1,v2,…,vk} as intermediate vertices does not use vk, Then
NOTE:
• If an element rij is 1 in R(k-1), it remains 1 in R(k)
• If an element rij is 0 in R(k-1), it has to be changed to 1 in R(k) if and only if the element in its row I and column k and the element in its column j and row k are both 1’s in R(k-1)
Algorithm:
Algorithm Warshall(A[1..n, 1..n])
// Computes transitive closure matrix
// Input: Adjacency matrix A
// Output: Transitive closure matrix R
Efficiency:
• Time efficiency is Θ(n3)
• Space efficiency: Requires extra space for separate matrices for recording intermediate results of the algorithm.
Comments
Post a Comment