How to Find the Actual Path Found by Bfs

How to trace the path in a Breadth-First Search?

You should have look at http://en.wikipedia.org/wiki/Breadth-first_search first.

---

Below is a quick implementation, in which I used a list of list to represent the queue of paths.

# graph is in adjacent list representation
graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }

def bfs(graph, start, end):
    # maintain a queue of paths
    queue = []
    # push the first path into the queue
    queue.append([start])
    while queue:
        # get the first path from the queue
        path = queue.pop(0)
        # get the last node from the path
        node = path[-1]
        # path found
        if node == end:
            return path
        # enumerate all adjacent nodes, construct a 
        # new path and push it into the queue
        for adjacent in graph.get(node, []):
            new_path = list(path)
            new_path.append(adjacent)
            queue.append(new_path)

print bfs(graph, '1', '11')

This prints: ['1', '4', '7', '11']

---

Another approach would be maintaining a mapping from each node to its parent, and when inspecting the adjacent node, record its parent. When the search is done, simply backtrace according the parent mapping.

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, []):
            if node not in queue :
                parent[adjacent] = node # <<<<< record its parent 
                queue.append(adjacent)

print bfs(graph, '1', '11')

The above codes are based on the assumption that there's no cycles.

How can I find the actual path found by BFS?

To do so, you need to store a map:V->V (from vertices to vertices), which will map from each node v, the vertex u that "discovered" v.

You will populate this map during the iterations of BFS.

Later - you can reconstruct the path by simply going from the target node (in the map) up until you get back to the source, which will be your path (reversed, of course).

Note that this map can be implemented as an array if you enumerate the vertices.

How does a Breadth-First Search work when looking for Shortest Path?

Technically, Breadth-first search (BFS) by itself does not let you find the shortest path, simply because BFS is not looking for a shortest path: BFS describes a strategy for searching a graph, but it does not say that you must search for anything in particular.

Dijkstra's algorithm adapts BFS to let you find single-source shortest paths.

In order to retrieve the shortest path from the origin to a node, you need to maintain two items for each node in the graph: its current shortest distance, and the preceding node in the shortest path. Initially all distances are set to infinity, and all predecessors are set to empty. In your example, you set A's distance to zero, and then proceed with the BFS. On each step you check if you can improve the distance of a descendant, i.e. the distance from the origin to the predecessor plus the length of the edge that you are exploring is less than the current best distance for the node in question. If you can improve the distance, set the new shortest path, and remember the predecessor through which that path has been acquired. When the BFS queue is empty, pick a node (in your example, it's E) and traverse its predecessors back to the origin. This would give you the shortest path.

If this sounds a bit confusing, wikipedia has a nice pseudocode section on the topic.

How to find the Final Path from the Traversal Path while performing BFS/DFS algorithm

One [out of many possible] approach is to maintain a map of target to source node. Every time you advance, record which source node was made to make that advance. So, in BFS case it will look like:

parents = {
  'A': NULL,
  'B': 'A',
  'C': 'A',
  'D': 'B',
  'E': 'B',
  'F': 'C',
  'G': 'C' 
}

Then, from the final node, reconstruct the path by going backward:

node = target
path = []
while node:
   path.append(node)
   node = parents[node]

Same approach works for DFS and Dijkstra

How to get the path between 2 nodes using Breadth-First Search?

In your node struct, you add a variable called parentNode which is the parent of that node in the path. In the end, you can retrieve the path by traversing from the goal node backward.

How can graph search return a path?

I will use your example:

        B
       / \
      1   2
     /     \
Start       D--5--Destination
     \     /
      1   1
       \ /
        C

Note that a pure Breadth-First Search pays no attention to edge weights (or cost). In this case, the first path that takes it to the destination might be Start->B->D->Destination.

It marks each node it visits with a boolean flag to indicate that the node has been visited, so that it doesn't pursue Start->B->Start->C->Start->... In order to remember the path that succeeded, we must store a little more information somewhere. One simple approach is to mark each node, not just with the visited flag, but with a reference to the node from which it was visited. So if the visitation order was Start, B, C, D, Destination, the graph will look like this:

        B(Start)
       / \
      1   2
     /     \
Start       D(B)--5--Destination(D)
     \     /
      1   1
       \ /
        C(Start)

Then we can backtrack. How did we get to Destination? From D. How did we get to D? From B. How did we get to B? from Start.

Breadth-First Search follows the first edge in the queue, and finds the shortest path (in the sense of smallest number of edges). If we want the least-weight (cheapest) path, we modify the search to keep track of cost-to-get-to-this-node, and follow the edge that reaches a new node most cheaply. (This is one version of Dijkstra's Algorithm.) Then in this case the visitation order will be the same, but we will visit D from C, not from B, and get the path Start->C->D->Destination.

With A*, using h(B) = 2, h(C) = 4, h(D) = 1, the visitation order is Start, B, D, C, D, Destination, and the path is Start->C->D->Destination.

Tracing and Returning a Path in Depth First Search

You are right - you cannot simply return the stack, it indeed contains a lot of unvisited nodes.

However, by maintaining a map (dictionary): map:Vertex->Vertex such that parentMap[v] = the vertex we used to discover v, you can get your path.

The modification you will need to do is pretty much in the for loop:

    for child in children:
        stack.push(child[0])
        parentMap[child] = parent #this line was added

Later on, when you found your target, you can get the path from the source to the target (pseudo code):

curr = target
while (curr != None):
  print curr
  curr = parentMap[curr]

Note that the order will be reversed, it can be solved by pushing all elements to a stack and then print.

I once answered a similar (though not identical IMO) question regarding finding the actual path in BFS in this thread

Another solution is to use a recursive version of DFS rather then iterative+stack, and once a target is found, print all current nodes in the recursion back up - but this solution requires a redesign of the algorithm to a recursive one.

---

P.S. Note that DFS might fail to find a path to the target (even if maintaining a visited set) if the graph contains an infinite branch.

If you want a complete (always finds a solution if one exists) and optimal (finds shortest path) algorithm - you might want to use BFS or Iterative Deepening DFS or even A* Algorithm if you have some heuristic function

---

Related Topics