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:
Initialize the boolean matrix with the provided graph values
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][i])
closure(i, j)
M[i][j] = 1
for k to graph[j].length
M[i, k] == false
closure( i, k)