---
title: "Transitive closure of 5-vertex graph (Warshall)"
subject: "Data Structure and Algorithm"
chapter: 10
key: "semester_4/data_structure_and_algorithm:transitive-closure-warshall-abcde"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/transitive-closure-warshall-abcde
site: BCT Engineering
---

# Transitive closure of 5-vertex graph (Warshall)

Data Structure and Algorithm · Chapter 10: Graphs

- Asked in: 2068 Magh, 8 marks
- Video: [Warshall's Algorithm To Find Transitive Closure | DP | Lec 59 | Design & Analysis of Algorithm](https://www.youtube.com/watch?v=fMpEsN1Dxek) — CSE Guru
- 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-warshall-abcde
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-10

## Question

Let G = (V, E) with V = {a, b, c, d, e} and E = {(a,c), (b,c), (b,d), (c,d), (d,e)} be a directed graph. Find the transitive closure of G using Warshall's algorithm, showing each iterations. Also draw initial and final graphs.

## Short answer

Using Warshall's algorithm, the transitive closure adds a→d, a→e, b→e, c→e. Final reachability: a reaches c,d,e; b reaches c,d,e; c reaches d,e; d reaches e; e reaches nothing.

## Answer

Vertices in order a, b, c, d, e. Edges: a→c, b→c, b→d, c→d, d→e. For each k in turn, P[i][j] = P[i][j] OR (P[i][k] AND P[k][j]).

#### Initial graph
```text
a --> c --> d --> e
      ^     ^
      |     |
      b ----+
   (b -> c and b -> d)
```

**P₀ (adjacency matrix)**

| | a | b | c | d | e |
|---|---|---|---|---|---|
| a | 0 | 0 | 1 | 0 | 0 |
| b | 0 | 0 | 1 | 1 | 0 |
| c | 0 | 0 | 0 | 1 | 0 |
| d | 0 | 0 | 0 | 0 | 1 |
| e | 0 | 0 | 0 | 0 | 0 |

**k = a:** no edge enters a, so no change.
**k = b:** no edge enters b, so no change.

**k = c:** into c: a, b. c's row has d. So a→d is added (b→d already exists).

| | a | b | c | d | e |
|---|---|---|---|---|---|
| a | 0 | 0 | 1 | 1 | 0 |
| b | 0 | 0 | 1 | 1 | 0 |
| c | 0 | 0 | 0 | 1 | 0 |
| d | 0 | 0 | 0 | 0 | 1 |
| e | 0 | 0 | 0 | 0 | 0 |

**k = d:** into d: a, b, c. d's row has e. So a→e, b→e and c→e are added.

| | a | b | c | d | e |
|---|---|---|---|---|---|
| a | 0 | 0 | 1 | 1 | 1 |
| b | 0 | 0 | 1 | 1 | 1 |
| c | 0 | 0 | 0 | 1 | 1 |
| d | 0 | 0 | 0 | 0 | 1 |
| e | 0 | 0 | 0 | 0 | 0 |

**k = e:** e has no outgoing edge, so no change. This is the final matrix (the transitive closure).

#### Final graph (transitive closure)
Edges: a→c, a→d, a→e, b→c, b→d, b→e, c→d, c→e, d→e (nine edges; the new ones are a→d, a→e, b→e, c→e).
```text
Original edges: a->c  b->c  b->d  c->d  d->e
Added edges:    a->d  a->e  b->e  c->e

Final graph (out-edges of each vertex):
 a ----> c, d, e
 b ----> c, d, e
 c ----> d, e
 d ----> e
 e       (no outgoing edges)
```
In words: a reaches c, d, e; b reaches c, d, e; c reaches d, e; d reaches e; e reaches nothing.

## Check yourself

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

1. In Warshall's algorithm, what condition adds the entry P[i][j] at iteration k?
   A. P[i][k] and P[k][j] are both 1
   B. k is greater than i
   C. P[i][j] is 0 only
   D. P[i][k] or P[k][j] is 1
   Answer: A. If i reaches k and k reaches j, then i reaches j. (Key point: Warshall rule)

2. Which edge is added at k = c?
   A. a->e
   B. c->e
   C. a->d
   D. b->e
   Answer: C. a and b enter c, c's row has d; a->d is new (b->d existed). (Key point: Iteration k = c)

3. Which edges are added at k = d?
   A. None
   B. a->d, b->d
   C. d->a, d->b
   D. a->e, b->e, c->e
   Answer: D. a, b, c all reach d and d reaches e, so each gains an edge to e. (Key point: Iteration k = d)

4. Why do k = a, k = b and k = e leave the matrix unchanged?
   A. Their rows are full
   B. These are the last vertices
   C. They are not in the graph
   D. a and b have no incoming edge and e has no outgoing edge
   Answer: D. The rule needs both an incoming path to k and an outgoing path from k. (Key point: Why k = a, b, e change nothing)

5. How many edges does the final transitive closure have, and which are new?
   A. 9; new ones a->d, a->e, b->e, c->e
   B. 9; new ones a->b, b->a, c->e, d->e
   C. 5; none new
   D. 10; new ones include e->a
   Answer: A. The original 5 edges plus 4 added edges make 9. (Key point: Final closure)

## Close variants set in other exams

- [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×