graph = {'1': ['2', '3', '4'], '2': ['5', '6'], '5': ['9', '10'], '4': ['7',
    '8'], '7': ['11', '12']}

def backtrace(parent, start, end):
    path = [end]
while path[-1] != start:
    path.append(parent[path[-1]])
path.reverse()
return path

def bfs(graph, start, end):
    parent = {}
queue = []
queue.append(start)
while queue:
    node = queue.pop(0)
if node == end:
    return backtrace(parent, start, end)
for adjacent in graph.get(node, []):
    parent[adjacent] = node
queue.append(adjacent)
print(bfs(graph, '1', '11'))
How to trace the path in a Breadth-First Search?