## Introduction

A Graph is a data structure that is used to represent networks and consists of two parts:

1. Nodes
2. Edges

### Graph Representation

1. Matrix
`A[i][j] = w`
where `w` - weight, `i` - source node, `j` - destination node

`A[i][..]`
where `i` - source node, `A[i]` - all the nodes reachable from `i`

## 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)
``````