797. All Paths From Source to Target

Problem

Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1, and return them in any order.

The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).

Example 1:

Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Example 2:

Input: graph = [[4,3,1],[3,2,4],[3],[4],[]]
Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

Example 3:

Input: graph = [[1],[]]
Output: [[0,1]]

Example 4:

Input: graph = [[1,2,3],[2],[3],[]]
Output: [[0,1,2,3],[0,2,3],[0,3]]

Example 5:

Input: graph = [[1,3],[2],[3],[]]
Output: [[0,1,2,3],[0,3]]

Constraints:

• n == graph.length
• 2 <= n <= 15
• 0 <= graph[i][j] < n
• graph[i][j] != i (i.e., there will be no self-loops).
• The input graph is guaranteed to be a DAG.

Discussion

We can interpret this question as searching on graph, finding paths from the same source node to the same target node. With different format of graphs, this problem is providing graph based on Adjacency List. DFS should be a good solution for this problem.

Solution

We perform DFS on the starting node 0, and search for all on-going edges down to the end node graph.length - 1. And as the graph is given as acyclic, there is no validation required on the paths. As long as the paths converges at the end node. We include the path into our result.

from typing import List

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        self.graph = graph
        self.result = []
        start = [0]
        path = []

        self.dfs(start, path)

        return self.result

    def dfs(self, next_nodes, path):
        if next_nodes:
            for node in next_nodes:
                if node == len(self.graph) - 1:
                    self.result.append(path + [node])
                else:
                    self.dfs(self.graph[node], path + [node])

Complexity Analysis

• Time Complexity: O(V + E), for DFS in a graph, wheres V is number of nodes and E is the number of edges.
• Space Complexity: O(V * E), for the result set in memory, which the number is determined by the number of edges, while the size is determined by the number of vertex.