/ Coding

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:

  1. Nodes
  2. Edges

Graph Representation

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

  2. Adjacency List
    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:

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)
What Experts Are Saying About Transitive Closure of a Graph
Share this

Subscribe to Coding Today

Popular queries