Teaching Kids Programming – Finding All Paths from Source to Target in a Directed Acyclic Graph (DAG) using Breadth First Search Algorithm


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]).

DAG Teaching Kids Programming - Finding All Paths from Source to Target in a Directed Acyclic Graph (DAG) using Breadth First Search Algorithm algorithms BFS graph python teaching kids programming youtube video

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

GD Star Rating
loading...
631 words
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

The Permanent URL is: Teaching Kids Programming – Finding All Paths from Source to Target in a Directed Acyclic Graph (DAG) using Breadth First Search Algorithm

Leave a Reply