from collections import deque
G = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D"],
    "D": []
}
parent = {}
def bfs(start, G):
    q = deque([start])
    parent = {start:None}
    while q:
        u = q.popleft()
        for v in G[u]:
            if v not in parent:
                parent[v] = u
                q.append(v)
                
    return parent
print(bfs('A',G))
def path_to(parent, target):
    # if target not in parent:
    #     return None
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]
print(path_to(bfs('A',G),'D'))
def dfs_recursive(u,G,visited=None):
    if visited is None:
        visited = set()
    visited.add(u)
    for v in G[u]:
        if v not in visited:
            dfs_recursive(v,G,visited)
    return visited
print(dfs_recursive('A',G))