Implementation and Comparison

Jeremy Zhang

Mar 14, 2020·3 min read

In the post here we implemented breadth first search and used it to find an optimal path in a 2D grid world. The implementation took 2 steps:

1. Going forward from the init state and record the expanding process
2. Going backward from the goal state to find the optimal path

One caveat is that the algorithm was not able to find multiple optimal path and the implementation is a bit lengthy. In this post, we will introduce more elegant and concise implementations of both breadth first search and depth first search.

Problem Settings

Suppose we have a graph setting as below:

our goal is to find all paths from A to F.

We then put the graph into a python dictionary:

BFS

The key of this breadth first search is still to:

1. Maintain a queue that is able to pop out the current lowest level node
2. Keep track of the trajectory

Remember that the lowest level node should always be considered first before exploring other nodes!

The implementation can simply be 9 lines of code:

path : the current nodes has been visited on that particular expansion

queue : maintains (current_node, current_path) and is able to pop out the node of the lowest level

Note that to avoid visit a node a second time, we only loop nodes in graph[vertex] — set(path) .

We can get the result:

list(bfs_paths(graph, "A", "F"))# [['A', 'C', 'F'], ['A', 'B', 'E', 'F']]

DFS

Different from breadth first search, it goes all the way to the deepest level before making and horizontal search.

Starting from the top, it goes all the way to the end on the leftmost branch and then retrieve back to the second last level and continue …

The key logic of the implementation is that starting from a node, as long as the node has child node, always expand the child node and repeat the same process until no more nodes.

As each step we are repeating the same process, we will use recursion here:

See how concise it is to use recursion to implement DFS. One example result would be:

list(dfs_paths(graph, "A", "E"))
# [['A', 'B', 'E'], ['A', 'C', 'F', 'E']]

Optimality of DFS

If we stop once we hit the target, DFS does not guarantee optimal result. As the example shown above, the first feasible solution returned by DFS of path (A, E) could be (A, C, F, E) (depending on the order of the searching trajectory). Clearly, the optimal path should be (A, B, E) .

An intuitively understanding could be, in contrast with BFS, which is a cautious guy who takes each step discreetly(not going any deeper until carefully checked all nodes in the same level), DFS is a bold guy who dares to go ahead without any concern of nodes in the same level.

Which is Better?

Finally, there is no algorithm outweighs the other in all scenarios. Which algorithm to apply always depends on your use case and computation budget. In cases where you really need an optimal solution and the tree is not super wide, BFS might be your choice. In cases you just need an solution and expanding the tree horizontally is computationally inefficient, you might need to consider DFS(there is a good explanation here).