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

Solution

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

 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);
            }
        }
    }
};

 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)
        }
    }
}

 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);
            }
        }
    }
}

 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)
            }
        }
    }
}

 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)

 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);
            }
        }
    }
}

 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

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

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

 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;
    }
};

 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
}

 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;
    }
}

 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
    }
}

 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

 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
    }
}

 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

⏰ 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#

Solution#

Method 1 - Depth-First Search#

Intuition#

Approach#

Code#

Complexity#

Method 2 - Floyd-Warshall Algorithm#

Intuition#

Approach#

Code#

Complexity#

Problem

Examples

Example 1

Example 2

Example 3

Solution

Method 1 - Depth-First Search

Intuition

Approach

Code

Complexity

Method 2 - Floyd-Warshall Algorithm

Intuition

Approach

Code

Complexity