Made Breadth First Search algorithm in Python. Don't know how to return solution

Question

I have manged to make a path-finding algorithm that expands like breadth-first, avoids revisiting nodes, and detect whether the goal node is found or not. However the main thing I am struggling with is one that finds a solution, the actual path from the starting node to the goal node. Basically everything works perfectly, but I don't know how to return the actual path from the starting node to the goal node.

By the way, in case you are wondering, this is not an assignment. I am self-teaching myself pathfinding algorithms (and AI in general) and am trying to recreate the breadth-first search algorithm. Therefore, I welcome psuedocode (as it would tell me what I am suppose to do and I can come up with the code on my own to learn a lot from it.)

Is it possible to return a solution (a path from start node to end node) with my algorithm? Do I have to rewrite my entire algorithm or is there a snippet of code that return the path from my breadth first search algorithm

import collections

def bfs(graph,start, end):
    path = collections.deque()
    trail = collections.deque()
    solution = collections.deque()


    path.append(start)

    # A series of visited nodes
    trail.append(start)

    if start == end:
        return path
    while True:
        for node in graph[start]:
            print node

            # Adds node to path if it is not visited already
            if node not in trail:
                path.append(node)
                trail.append(node)
                print path        

        #Removes parent node after all children added to path (by removing the left of the path)
        path.popleft()
        start = path.popleft()
        path.appendleft(start)
        print "****Node Scan Completed:****"
        print path

        # If goal node is reached
        if start == end:
            print "----------------------Final Results:----------------------"
            print trail
            print path
            return solution
    print "Final Results:"
    print trail
    print path
    return None


graph = { "a" : [],
          "b" : ["a"],
          "c" : ["a"],
          "d" : ["b","c","e"],
          "e" : ["h","r"],
          "f" : ["c","g"],
          "g" : [],
          "h" : ["p","q"],
          "p" : ["q"],
          "q" : [],
          "r" : ["f"],
          "s" : ["d","e","p"]
        }

print bfs(graph,'s','g')

Answer 1

First of all, kudos to you for taking the time to learn things by yourself.

Your algorithm is missing one very important piece: as you've already realized, you're not saving the information about the path from the starting node to the ending node. You're only storing the visited nodes (in the trail variable) and the nodes to visit (in the path) variable. The solution is very simple. Simply add a map of parent nodes, so whenever you visit a node, you know which node you were coming from. Once you reach the ending node, you can check this map of parent nodes, building the solution path until you arrive to the starting node.

In code, just add a new parents map at the very top:

path = collections.deque()
trail = collections.deque()
parents = {} # New line

Next, add the code to fill this map within the loop:

        # Adds node to path if it is not visited already
        if node not in trail:
            parents[node] = start # New line
            path.append(node)
            trail.append(node)

And finally add the code to build and return the solution at the bottom of your function:

    # If goal node is reached
    if start == end:
        print "----------------------Final Results:----------------------"
        print trail
        print path

        solution = [end] # New code from here down
        n = end
        while n in parents and parents[n]:
            solution.append(parents[n])
            n = parents[n]

        return solution[::-1]

You can find the entire code here.