What Experts Are Saying About Transitive Closure of a Graph
Introduction
A Graph is a data structure that is used to represent networks and consists of two parts:
 Nodes
 Edges
Graph Representation

Matrix
A[i][j] = w
wherew
 weight,i
 source node,j
 destination node 
Adjacency List
A[i][..]
wherei
 source node,A[i]
 all the nodes reachable fromi
Transitive Closure of Graph
The transitive closure of a graph is a measure of, which vertices are reachable from other vertices.
Representation
matrix M, where M[i][j] == 1 if there is a path between vertices i and j, and otherwise 0.
Example
For example, suppose we are given the following graph in the adjacency list form:
graph = [
[0, 1, 3],
[1, 2],
[2],
[3]
]
The transitive closure of this graph would be:
[1, 1, 1, 1]
[0, 1, 1, 0]
[0, 0, 1, 0]
[0, 0, 0, 1]
Solutions
Brute Approach:
for i to graph.length
graphRow = graph[i]
for j to graphRow.length
M[i][graphRow[j]] = 1
1 1 0 1
0 1 1 0
0 0 1 0
0 0 0 1
for i to graph.length
graphRow = graph[i]
for j to graphRow.length
if i != graphRow[j]
for k to M.Rows.length
M[i][k] = M[i][k]  M[graphRow[j]][k]
1 1 1 1
0 1 1 0
0 0 1 0
0 0 0 1
DFS approach
The optimized approach to the problem would be the Depth First
for i to graph.length
closure(i, graph[i][0])
closure(i, j)
M[i][j] = 1
for k to graph[j].length
M[i, k] == false
closure( i, k)
Subscribe to Coding Today
Get the latest posts delivered right to your inbox