from collections import deque
def dfs_gsa(graph, start, goal, trace=False):
    frontier = deque([start])
    explored = set()
    while frontier:
        path = frontier.pop()
        state = path[-1]
        if state == goal: return path
        if state in explored: continue
        explored.add(state)
        paths = [path + child for child in graph[state]]
        frontier.extend(paths)
        if trace:
            print(f"{path} -> {list(frontier)}")
            print(f"explored: {sorted(explored)}\n")
practice = {"S": ["a", "d", "G"], "a": ["b"],
            "d": ["b", "e"], "b": ["c", "e"],
            "c": ["G"], "e": ["G"], "G": []}
print("solution:", dfs_gsa(practice, "S", "G", True))