Transitive Closure of a Graph

Problem

The transitive closure of a graph is a measure of which vertices are reachable from other vertices. It can be represented as a matrix M, where M[i][j] == 1 if there is a path between vertices i and j, and otherwise 0.

Given a graph, find its transitive closure.

Examples

Example 1

1
2
3
4
5
6
7


Input: graph = [[0, 1, 3], [1, 2], [2], [3]]
Output: [[1, 1, 1, 1], [0, 1, 1, 0], [0, 0, 1, 0], [0, 0, 0, 1]]
Explanation: 
- From vertex 0: can reach 0 (self), 1 (direct), 2 (via 1), 3 (direct)
- From vertex 1: can reach 1 (self), 2 (direct), but not 0 or 3
- From vertex 2: can only reach 2 (self)
- From vertex 3: can only reach 3 (self)

Example 2

1
2
3


Input: graph = [[1], [2], [0]]
Output: [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
Explanation: This is a cycle where all vertices can reach all other vertices

Example 3

1
2
3
4
5


Input: graph = [[1], []]
Output: [[0, 1], [0, 0]]
Explanation: 
- From vertex 0: can reach 1 (direct) but not itself
- From vertex 1: cannot reach any vertex

Method 1 - Depth-First Search

Intuition

For each vertex, we can perform a DFS to find all vertices reachable from it. The transitive closure matrix will have M[i][j] = 1 if vertex j is reachable from vertex i.

Approach

Initialize a result matrix of size n x n with all zeros
For each vertex i from 0 to n-1:
- Perform DFS starting from vertex i
- Mark all reachable vertices in the result matrix
- Use a visited array to avoid cycles and redundant work
During DFS from vertex i, for each reachable vertex j, set result[i][j] = 1
Return the result matrix

Code

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
public:
    vector<vector<int>> transitiveClosure(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<vector<int>> ans(n, vector<int>(n, 0));
        
        for (int i = 0; i < n; i++) {
            vector<bool> vis(n, false);
            dfs(graph, i, i, ans, vis);
        }
        
        return ans;
    }
    
private:
    void dfs(vector<vector<int>>& graph, int src, int curr, vector<vector<int>>& ans, vector<bool>& vis) {
        vis[curr] = true;
        ans[src][curr] = 1;
        
        for (int next : graph[curr]) {
            if (!vis[next]) {
                dfs(graph, src, next, ans, vis);
            }
        }
    }
};

Go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


func transitiveClosure(graph [][]int) [][]int {
    n := len(graph)
    ans := make([][]int, n)
    for i := range ans {
        ans[i] = make([]int, n)
    }
    
    for i := 0; i < n; i++ {
        vis := make([]bool, n)
        dfs(graph, i, i, ans, vis)
    }
    
    return ans
}

func dfs(graph [][]int, src, curr int, ans [][]int, vis []bool) {
    vis[curr] = true
    ans[src][curr] = 1
    
    for _, next := range graph[curr] {
        if !vis[next] {
            dfs(graph, src, next, ans, vis)
        }
    }
}

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
    public int[][] transitiveClosure(int[][] graph) {
        int n = graph.length;
        int[][] ans = new int[n][n];
        
        for (int i = 0; i < n; i++) {
            boolean[] vis = new boolean[n];
            dfs(graph, i, i, ans, vis);
        }
        
        return ans;
    }
    
    private void dfs(int[][] graph, int src, int curr, int[][] ans, boolean[] vis) {
        vis[curr] = true;
        ans[src][curr] = 1;
        
        for (int next : graph[curr]) {
            if (!vis[next]) {
                dfs(graph, src, next, ans, vis);
            }
        }
    }
}

Kotlin

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
    fun transitiveClosure(graph: Array<IntArray>): Array<IntArray> {
        val n = graph.size
        val ans = Array(n) { IntArray(n) }
        
        for (i in 0 until n) {
            val vis = BooleanArray(n)
            dfs(graph, i, i, ans, vis)
        }
        
        return ans
    }
    
    private fun dfs(graph: Array<IntArray>, src: Int, curr: Int, ans: Array<IntArray>, vis: BooleanArray) {
        vis[curr] = true
        ans[src][curr] = 1
        
        for (next in graph[curr]) {
            if (!vis[next]) {
                dfs(graph, src, next, ans, vis)
            }
        }
    }
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def transitiveClosure(self, graph: List[List[int]]) -> List[List[int]]:
        n = len(graph)
        ans = [[0] * n for _ in range(n)]
        
        for i in range(n):
            vis = [False] * n
            self.dfs(graph, i, i, ans, vis)
        
        return ans
    
    def dfs(self, graph: List[List[int]], src: int, curr: int, ans: List[List[int]], vis: List[bool]) -> None:
        vis[curr] = True
        ans[src][curr] = 1
        
        for next_node in graph[curr]:
            if not vis[next_node]:
                self.dfs(graph, src, next_node, ans, vis)

Rust

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


impl Solution {
    pub fn transitive_closure(graph: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let n = graph.len();
        let mut ans = vec![vec![0; n]; n];
        
        for i in 0..n {
            let mut vis = vec![false; n];
            Self::dfs(&graph, i, i, &mut ans, &mut vis);
        }
        
        ans
    }
    
    fn dfs(graph: &Vec<Vec<i32>>, src: usize, curr: usize, ans: &mut Vec<Vec<i32>>, vis: &mut Vec<bool>) {
        vis[curr] = true;
        ans[src][curr] = 1;
        
        for &next in &graph[curr] {
            let next = next as usize;
            if !vis[next] {
                Self::dfs(graph, src, next, ans, vis);
            }
        }
    }
}

TypeScript

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
    transitiveClosure(graph: number[][]): number[][] {
        const n = graph.length;
        const ans: number[][] = Array(n).fill(null).map(() => Array(n).fill(0));
        
        for (let i = 0; i < n; i++) {
            const vis: boolean[] = Array(n).fill(false);
            this.dfs(graph, i, i, ans, vis);
        }
        
        return ans;
    }
    
    private dfs(graph: number[][], src: number, curr: number, ans: number[][], vis: boolean[]): void {
        vis[curr] = true;
        ans[src][curr] = 1;
        
        for (const next of graph[curr]) {
            if (!vis[next]) {
                this.dfs(graph, src, next, ans, vis);
            }
        }
    }
}

Complexity

⏰ Time complexity: O(V * (V + E)), where V is the number of vertices and E is the number of edges. We perform DFS from each vertex, and each DFS takes O(V + E) time
🧺 Space complexity: O(V²), for the result matrix and O(V) for the visited array and recursion stack

Method 2 - Floyd-Warshall Algorithm

Intuition (Floyd-Warshall)

The Floyd-Warshall algorithm can be adapted to compute transitive closure. Instead of finding shortest paths, we determine reachability between all pairs of vertices.

Approach (Floyd-Warshall)

Convert the adjacency list to an adjacency matrix
Initialize the transitive closure matrix where M[i][j] = 1 if there’s a direct edge from i to j
Add self-loops: M[i][i] = 1 for all vertices
Apply Floyd-Warshall: for each intermediate vertex k, if there’s a path from i to k and from k to j, then there’s a path from i to j
Return the result matrix

Code (Floyd-Warshall)

C++ (Floyd-Warshall)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
public:
    vector<vector<int>> transitiveClosure(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<vector<int>> ans(n, vector<int>(n, 0));
        
        // Initialize direct edges
        for (int i = 0; i < n; i++) {
            for (int j : graph[i]) {
                ans[i][j] = 1;
            }
            ans[i][i] = 1; // Self-loop
        }
        
        // Floyd-Warshall for reachability
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    ans[i][j] = ans[i][j] || (ans[i][k] && ans[k][j]);
                }
            }
        }
        
        return ans;
    }
};

Go (Floyd-Warshall)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


func transitiveClosure(graph [][]int) [][]int {
    n := len(graph)
    ans := make([][]int, n)
    for i := range ans {
        ans[i] = make([]int, n)
    }
    
    // Initialize direct edges
    for i := 0; i < n; i++ {
        for _, j := range graph[i] {
            ans[i][j] = 1
        }
        ans[i][i] = 1 // Self-loop
    }
    
    // Floyd-Warshall for reachability
    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if ans[i][k] == 1 && ans[k][j] == 1 {
                    ans[i][j] = 1
                }
            }
        }
    }
    
    return ans
}

Java (Floyd-Warshall)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
    public int[][] transitiveClosure(int[][] graph) {
        int n = graph.length;
        int[][] ans = new int[n][n];
        
        // Initialize direct edges
        for (int i = 0; i < n; i++) {
            for (int j : graph[i]) {
                ans[i][j] = 1;
            }
            ans[i][i] = 1; // Self-loop
        }
        
        // Floyd-Warshall for reachability
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    ans[i][j] = ans[i][j] | (ans[i][k] & ans[k][j]);
                }
            }
        }
        
        return ans;
    }
}

Kotlin (Floyd-Warshall)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
    fun transitiveClosure(graph: Array<IntArray>): Array<IntArray> {
        val n = graph.size
        val ans = Array(n) { IntArray(n) }
        
        // Initialize direct edges
        for (i in 0 until n) {
            for (j in graph[i]) {
                ans[i][j] = 1
            }
            ans[i][i] = 1 // Self-loop
        }
        
        // Floyd-Warshall for reachability
        for (k in 0 until n) {
            for (i in 0 until n) {
                for (j in 0 until n) {
                    ans[i][j] = ans[i][j] or (ans[i][k] and ans[k][j])
                }
            }
        }
        
        return ans
    }
}

Python (Floyd-Warshall)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def transitiveClosure(self, graph: List[List[int]]) -> List[List[int]]:
        n = len(graph)
        ans = [[0] * n for _ in range(n)]
        
        # Initialize direct edges
        for i in range(n):
            for j in graph[i]:
                ans[i][j] = 1
            ans[i][i] = 1  # Self-loop
        
        # Floyd-Warshall for reachability
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    ans[i][j] = ans[i][j] or (ans[i][k] and ans[k][j])
        
        return ans

Rust (Floyd-Warshall)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


impl Solution {
    pub fn transitive_closure(graph: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let n = graph.len();
        let mut ans = vec![vec![0; n]; n];
        
        // Initialize direct edges
        for i in 0..n {
            for &j in &graph[i] {
                ans[i][j as usize] = 1;
            }
            ans[i][i] = 1; // Self-loop
        }
        
        // Floyd-Warshall for reachability
        for k in 0..n {
            for i in 0..n {
                for j in 0..n {
                    ans[i][j] = ans[i][j] | (ans[i][k] & ans[k][j]);
                }
            }
        }
        
        ans
    }
}

TypeScript (Floyd-Warshall)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
    transitiveClosure(graph: number[][]): number[][] {
        const n = graph.length;
        const ans: number[][] = Array(n).fill(null).map(() => Array(n).fill(0));
        
        // Initialize direct edges
        for (let i = 0; i < n; i++) {
            for (const j of graph[i]) {
                ans[i][j] = 1;
            }
            ans[i][i] = 1; // Self-loop
        }
        
        // Floyd-Warshall for reachability
        for (let k = 0; k < n; k++) {
            for (let i = 0; i < n; i++) {
                for (let j = 0; j < n; j++) {
                    ans[i][j] = ans[i][j] || (ans[i][k] && ans[k][j]);
                }
            }
        }
        
        return ans;
    }
}

Complexity (Floyd-Warshall)

⏰ Time complexity: O(V³), due to the three nested loops in Floyd-Warshall algorithm
🧺 Space complexity: O(V²), for the result matrix

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Method 1 - Depth-First Search#

Intuition#

Approach#

Code#

C++#

Go#

Java#

Kotlin#

Python#

Rust#

TypeScript#

Complexity#

Method 2 - Floyd-Warshall Algorithm#

Intuition (Floyd-Warshall)#

Approach (Floyd-Warshall)#

Code (Floyd-Warshall)#

C++ (Floyd-Warshall)#

Go (Floyd-Warshall)#

Java (Floyd-Warshall)#

Kotlin (Floyd-Warshall)#

Python (Floyd-Warshall)#

Rust (Floyd-Warshall)#

TypeScript (Floyd-Warshall)#

Complexity (Floyd-Warshall)#