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

image

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

image

image

image

Efficiency:

• Time efficiency is Θ(n3)

• Space efficiency: Requires extra space for separate matrices for recording intermediate results of the algorithm.

Comments

Popular posts from this blog

Data Structure Visualization:Introduction and Value of Data Structure Rendering

Binary Space Partitioning Trees:BSP Tree as a Hierarchy of Regions.

Drawing Trees:HV-Layout