Breadth First Search and Depth First Search
In this exercise we will continue with previous British museum example, and we will try to implement Breadth first search (BFS), and Depth first search (DFS). We will use the same grid word and same start and finish positions.
Grid word with start, finish and red obstacles
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. The algorithm goes as followed:
- To find actual node position, take a look at the all expanded nodes, and pick the one with the highest index.
- Expand the actual node (with highest index), and add all valid nodes (nodes that are not already expanded, are not outside of the grid or are not obstacles) with corresponding depth value (computed as actual node depth +1)
- Repeat until the solution is found.
The algorithm can also be expressed with queue mechanism, where you initialize your que, with start position. You expand the first element and add all valid nodes into the front of queue. You also remove the actual node from a queue, and you put him into the memory bank with actual depth. All expanded nodes should be expanded with depth computed as actual node depth +1. You repeat the same process with a next element in queue, until the finish is found.
On the other hand, the BFS algorithm uses the opposite strategy as depth-first search, which instead explores the highest-depth nodes first before being forced to backtrack and expand shallower nodes. The algorithm is expressed as:
- Take actual node as the node with a minimal depth (from all expanded nodes)
- Expand the actual node (with lowest index), and add all valid nodes (nodes that are not already expanded, are not outside of the grid or are not obstacles) with corresponding depth value (computed as actual node depth +1)
- Repeat until the solution is found.
In fact, the algorithm can be expressed with a que mechanics, that is 99% similar to DFS, but instead of adding an element into the front of queue, we just put the element into the end of the queue, so the nodes with the lowest depth are expanded first.
| Data | Value |
|---|---|
| Source | https://en.wikipedia.org/wiki/Breadth-first_search |
| Code | 5_BFS_DFS_code.zip |
| Solution code | 5_BFS_DFS_solution_code.zip |