Teaching Kids Programming: Videos on Data Structures and Algorithms
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).
All the elements of graph[i] are unique.
The input graph is guaranteed to be a DAG.
Finding All Paths from Source to Target in a Directed Acyclic Graph (DAG) using Breadth First Search Algorithm
Breadth First Search Algorithm can be used to traverse a Graph. We keep tracking of the current Node and the path followed so far. The graph is DAG – hence there isn’t cycles and we don’t need to manually avoid re-visiting same nodes.
Each node in the worst case, connects to other greater nodes. The total paths could be 2^(N-1)-1. Considering O(N) time to build a path, total complexity is O(N*2^N). The space complexity is O(N*2^N+N) if we are considering the space to store all the paths. Otherwise, the space complexity is O(N) for a de-queue.
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution: def allPathsSourceTarget(self, G: List[List[int]]) -> List[List[int]]: ans = [] n = len(G) q = deque([(0, [0])]) while q: curNode, curPath = q.popleft() if curNode == n - 1: ans.append(curPath) for nextNode in G[curNode]: q.append((nextNode, curPath + [nextNode])) return ans |
class Solution: def allPathsSourceTarget(self, G: List[List[int]]) -> List[List[int]]: ans = [] n = len(G) q = deque([(0, [0])]) while q: curNode, curPath = q.popleft() if curNode == n - 1: ans.append(curPath) for nextNode in G[curNode]: q.append((nextNode, curPath + [nextNode])) return ans
The current node is the last node in the current path, thus we can simply push a list of nodes (current path) into the queue.
1 2 3 4 5 6 7 8 9 10 11 12 13 | class Solution: def allPathsSourceTarget(self, G: List[List[int]]) -> List[List[int]]: ans = [] n = len(G) q = deque([[0]]) while q: curPath = q.popleft() curNode = curPath[-1] if curNode == n - 1: ans.append(curPath) for nextNode in G[curNode]: q.append(curPath + [nextNode]) return ans |
class Solution: def allPathsSourceTarget(self, G: List[List[int]]) -> List[List[int]]: ans = [] n = len(G) q = deque([[0]]) while q: curPath = q.popleft() curNode = curPath[-1] if curNode == n - 1: ans.append(curPath) for nextNode in G[curNode]: q.append(curPath + [nextNode]) return ans
Remember, this problem can be solved by Recursive Depth First Search Algorithm: Teaching Kids Programming – Finding All Paths from Source to Target in a Directed Acyclic Graph (DAG) using Recursive Depth First Search Algorithm
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Finding All Paths from Source to Target in a Directed Acyclic Graph (DAG) using Recursive Depth First Search Algorithm
Next Post: Teaching Kids Programming - Disjoint Set: Find if Path Exists in Graph via Union Find Algorithm