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

# Transitive closure of 4-vertex graph (Warshall)

Data Structure and Algorithm · Chapter 10: Graphs

- Asked in: 2068 Bhadra, 6 marks
- Video: [Warshall's Algorithm (Finding the Transitive Closure)](https://www.youtube.com/watch?v=_-p8zhizock) — Neso Academy
- 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-abcd
- 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} and E = {(a,d), (b,a), (b,c), (c,a), (c,d), (d,c)} be a directed graph. Find the transitive closure of G using Warshall's algorithm, showing each iterations.

## Short answer

Using Warshall's algorithm, the transitive closure adds edges: a→a, a→c, a→d; b→a, b→c, b→d; c→a, c→c, c→d; d→a, d→c, d→d. No vertex reaches b.

## Answer

Warshall's algorithm: for k = a, b, c, d in turn, set P[i][j] = P[i][j] OR (P[i][k] AND P[k][j]). That is, if i reaches k and k reaches j, then i reaches j.

Vertices in order a, b, c, d. Edges: a→d, b→a, b→c, c→a, c→d, d→c.

**P₀ (adjacency matrix)**

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

**Iteration k = a** (vertices with an edge into a: b, c; a's row has d): b→d added; c→d already present.

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

**Iteration k = b** (no edge enters b): no change.

**Iteration k = c** (into c: b, d; c's row has a, d): b already has a, d; d gains a and d.

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

**Iteration k = d** (into d: a, b, c, d; d's row has a, c, d): every row gains a, c, d.

**Transitive closure P₄**

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

**Answer:** closure edges are a→a, a→c, a→d; b→a, b→c, b→d; c→a, c→c, c→d; d→a, d→c, d→d. No vertex reaches b, because b has no incoming edge.

## Check yourself

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

1. What is Warshall's update rule for iteration k?
   A. P[i][j] = min(P[i][j], P[i][k] + P[k][j])
   B. P[i][j] = P[i][j] + P[i][k]
   C. P[i][j] = P[i][j] AND P[k][k]
   D. P[i][j] = P[i][j] OR (P[i][k] AND P[k][j])
   Answer: D. If i reaches k and k reaches j, then i reaches j. (Key point: Warshall update rule)

2. What is added at k = a?
   A. b->d
   B. a->c
   C. Nothing
   D. d->a
   Answer: A. b and c have edges into a, and a's row has d, so b->d is added (c->d already exists). (Key point: Iteration k = a)

3. Why does k = b change nothing?
   A. b is the first vertex
   B. No edge enters b, so no vertex reaches b
   C. b has no outgoing edges
   D. b is isolated
   Answer: B. The rule needs P[i][b] = 1 for some i, and nobody reaches b. (Key point: Iteration k = b)

4. In the final closure, why is column b all zeros?
   A. Warshall ignores b
   B. No vertex can reach b because it has no incoming edge
   C. b reaches itself only
   D. b was removed
   Answer: B. Closure only adds paths, and no path can end at b. (Key point: Why column b is zero)

5. Which statement about the final closure is correct?
   A. Only a reaches d
   B. d cannot reach a
   C. a, c and d all reach a, c, d; b reaches a, c, d
   D. b is reached by a
   Answer: C. a->d->c->a forms a cycle, so a, c, d reach each other and themselves; b reaches them through b->a and b->c. (Key point: Final result)

## Close variants set in other exams

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