---
title: "Transitive closure"
subject: "Data Structure and Algorithm"
chapter: 10
key: "semester_4/data_structure_and_algorithm:transitive-closure-definition"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/transitive-closure-definition
site: BCT Engineering
---

# Transitive closure

Data Structure and Algorithm · Chapter 10: Graphs

- Asked in: 2070 Magh, 2 marks
- Video: [Transitive closure of a Graph (Reachability Matrix) #Graph Theory 8](https://www.youtube.com/watch?v=sioNsVeSbQo) — Vivekanand Khyade - Algorithm Every Day
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/transitive-closure-definition
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-10

## Question

What is transitive closure?

## Short answer

Transitive closure of a directed graph G is a graph G* with an edge (i,j) whenever a path from i to j exists in G. It is represented as a Boolean matrix and computed by Warshall's algorithm in O(n³).

## Answer

The **transitive closure** of a directed graph G = (V, E) is a graph G\* = (V, E\*) that has an edge (i, j) whenever there is a path of any length from vertex i to vertex j in G. It is stored as a Boolean matrix P where P[i][j] = 1 if j is reachable from i. It tells which vertices can reach which others, and is computed with Warshall's algorithm in O(n³).

Example: edges a→b, b→c give transitive closure edges a→b, b→c and a→c.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. When does the transitive closure G* contain edge (i, j)?
   A. When i and j have the same degree
   B. Whenever there is a path of any length from i to j in G
   C. Only when (i, j) is already an edge in G
   D. Only when the path has length exactly 2
   Answer: B. G* has an edge (i, j) for any path from i to j. (Key point: Closure definition)

2. How is the transitive closure stored?
   A. As a Boolean matrix P where P[i][j] = 1 if j is reachable from i
   B. As a spanning tree
   C. As a sorted edge-weight list
   D. As a stack of visited vertices
   Answer: A. A Boolean reachability matrix is used. (Key point: Representation)

3. For edges a->b and b->c, which edge is added in the closure?
   A. b->a
   B. a->a
   C. a->c
   D. c->a
   Answer: C. a reaches c through b, so a->c is added. (Key point: Example)

4. Which algorithm computes transitive closure, and in what time?
   A. Prim's, O(n)
   B. Warshall's, O(n^3)
   C. Kruskal's, O(E log E)
   D. Dijkstra's, O(n^2)
   Answer: B. Warshall's algorithm uses three nested loops, O(n^3). (Key point: Algorithm)

## Related in Data Structure and Algorithm

- [Transitive closure of 4-vertex graph (Warshall)](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atransitive-closure-warshall-abcd) — Data Structure and Algorithm, chapter 10, asked 2×
- [Transitive closure of 5-vertex graph (Warshall)](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atransitive-closure-warshall-abcde) — Data Structure and Algorithm, chapter 10, asked 2×