PadhaikoAll subjects

Past exam question: 2066 Jestha (Back), Q10(b)

Data Structure and Algorithms · 4 marks

Open in the Padhaiko app

Topic: Graphs

Question

Write short notes on: b) Transitive Closure Graph

Solution

Transitive Closure of a Directed Graph: Given a directed graph , its transitive closure is a directed graph (often represented as an reachability matrix ) such that there is a directed edge (i.e., ) if and only if there exists a directed path of length from vertex to vertex in .

Answer:

The transitive closure connects whenever is reachable from via one or more directed edges in , computed in time by Warshall's algorithm.

All past exam questions for Data Structure and Algorithms