In this post, I introduce two fundamental search algorithms used to traverse or search through graphs or tree data structures: breadth-first search (BFS), and depth-first search (DFS). I also present an overview of a path/search navigation scripts for both algorithms and compare their metrics.
This post builds on my earlier post about stack and queue because those approaches are at the heart of the BFS and DFS implementation. You can find that post here and I highy recommend giving it a glance first.
We’ll delve into the definitions and examples below, but first, take a quick look at the following clips showing a seeker (ladybug) traversing a 5×5 grid using BFS algorithm and DFS algorithm. I also discuss the simulation scripts later in this post.
BFS simulation snippet from my script:
The following shows a seeker (ladybug) traversing a 5×5 grid using DFS algorithm. It’s a snapshot from one of the simulation scripts (discussed below).
DFS simulation snippet from my script:
It may not seem like there’s any difference between the two in a small grid with a straight-forward layout but there is when we set off the seeker to explore larger spaces from different starting points. We’ll look at some metrics below and you will have the opportunity to run them both starting at random locations!.
While we’re not going to go very deep into the algorithms here, I intend to give you a high-level overview of each, enough to appreciate the algorithms and their uses and be more curious to learn more.
BFS (Breadth-first Search)
The Breadth-First Search (BFS) algorithm is a fundamental technique used to traverse or search through tree data structures.
How BFS Works
Initialization:
- Start from a given source node.
- Use a queue to keep track of nodes to be explored.
- Mark the source node as visited and enqueue it.
Exploration:
- While the queue is not empty:
- Dequeue a node from the front of the queue.
- Visit this node (e.g., process its value).
- For each unvisited neighbor of this node:
- Mark the neighbor as visited.
- Enqueue the neighbor.
Termination:
- The process continues until the queue is empty, ensuring all nodes are visited in a breadth-first manner.
BFS Traversal Example:
Imagine we have the following graph:
A
/ \
B C
/ \ \
D E F
Starting from node A:
- Enqueue A and mark it as visited.
- Dequeue A, visit it, and enqueue its neighbors B and C.
- Dequeue B, visit it, and enqueue its neighbors D and E.
- Dequeue C, visit it, and enqueue its neighbor F.
- Continue this process until all nodes are visited.
The order of visiting nodes would be: A -> B -> C -> D -> E -> F.
Applications of BFS:
• Shortest Path in Unweighted Graphs: BFS can find the shortest path between two nodes in an unweighted graph.
• Cycle Detection: BFS can be used to detect cycles in both directed and undirected graphs.
• Level Order Traversal: In binary trees, BFS is used for level order traversal.
Learn more about BFS @ https://en.wikipedia.org/wiki/Breadth-first_search
DFS (Depth-first search)
Depth-First Search (DFS) is a fundamental algorithm used to traverse or search through graph or tree data structures.
How DFS Works
Initialization:
- Start from a given source node.
- Use a stack to keep track of nodes to be explored (or use recursion, which implicitly uses the call stack).
- Mark the source node as visited.
Exploration:
While there are nodes to explore:
- Pop a node from the stack (or process the current node in recursion).
- Visit this node (e.g., process its value).
- For each unvisited neighbor of this node:
- Mark the neighbor as visited.
- Push the neighbor onto the stack (or call the recursive function for the neighbor).
Termination:
- The process continues until there are no more nodes to explore, ensuring all nodes are visited in a depth-first manner.
DFS Traversal Example:
Imagine we have the following graph:
A
/ \
B C
/ \ \
D E F
Starting from node A:
- Push A onto the stack and mark it as visited.
- Pop A, visit it, and push its neighbors B and C onto the stack.
- Pop C, visit it, and push its neighbor F onto the stack.
- Pop F, visit it (no more neighbors to push).
- Pop B, visit it, and push its neighbors D and E onto the stack.
- Continue this process until all nodes are visited.
In Depth-First Search (DFS), the order of visiting nodes depends on the implementation details (such as whether you use a stack or recursion) and the order in which you explore the neighbors of each node.
If we start at node A and explore the left child first, the DFS order would be: A -> B -> D -> E -> C -> F. However, if we start at node A and explore the right child first, the DFS order would be: A -> C -> F -> B -> E -> D
Applications of DFS:
Solving Puzzles: Such as mazes or Sudoku.
Path Finding: DFS can be used to find a path between two nodes in a graph.
Topological Sorting: Useful in scheduling tasks.
Cycle Detection: DFS can detect cycles in both directed and undirected graphs.
Learn more about DFS @ https://en.wikipedia.org/wiki/Depth-first_search
When to use BFS vs DFS?
Both BFS and DFS have the same time complexity of (O(V + E)), where (V) is the number of vertices and (E) is the number of edges in the graph. This is because both algorithms need to visit every vertex and edge in the worst case. However, they differ in their approach and use cases:
- BFS: Uses a queue and explores all neighbors at the present depth level before moving on to nodes at the next depth level. It’s particularly useful for finding the shortest path in unweighted graphs and for level-order traversal in trees.
- DFS: Uses a stack (or recursion) and explores as far as possible along each branch before backtracking. It’s useful for tasks like topological sorting, solving puzzles, and detecting cycles in graphs.
So, while they share the same complexity, their different strategies make them suitable for different types of problems.
Which one is more efficient?
The efficiency of BFS (Breadth-First Search) and DFS (Depth-First Search) depends on the specific context. Here are some key points:
BFS (Breadth-First Search):
• Time Complexity: Generally, BFS has a time complexity of (O(V + E)), where (V) is the number of vertices and (E) is the number of edges.
• Space Complexity: BFS can be more memory-intensive because it stores all the nodes at the current level before moving on to the next level.
• Optimality: BFS is optimal for finding the shortest path in an unweighted graph.
DFS (Depth-First Search):
- Time Complexity: DFS also has a time complexity of (O(V + E)).
- Space Complexity: DFS is generally more memory-efficient because it only needs to store the nodes along the current path.
- Optimality: DFS is not guaranteed to find the shortest path but can be faster in scenarios where the solution is deep in the graph.
Practical Considerations:
- Grid Size: For smaller grids, the difference in efficiency might be negligible. However, for larger grids, BFS could become more memory-intensive.
- Path Characteristics: If you need the shortest path, BFS is more suitable. If you are exploring all possible paths or the solution is deep, DFS might be more efficient.
In summary, for the shortest path and when memory is not an issue, BFS is more efficient. If memory is a concern or the solution is deep, DFS might be more efficient.
Do both take the same number of moves to visit all cells in a grid of same size?
Both BFS and DFS will generally require the same number of moves. This is because both algorithms will eventually visit every cell in the grid, and the total number of cells to be visited remains constant. However, the order in which the cells are visited will differ between BFS and DFS:
BFS: Visits all nodes at the current depth level before moving on to nodes at the next depth level. This means it explores the grid level by level.
DFS: Explores as far as possible along each branch before backtracking. This means it goes deep into one branch before moving to another.
While the total number of moves (or steps) to visit all cells will be the same, the path taken and the sequence of visited cells will be different. This can affect the intermediate states and the appearance of the exploration process.
Moves required by each algorithm to visit ALL cells in a given grid: (experimented with tkinter-pathBFS.py and tkinter-pathDFS.py ]
Moves required by each algorithm to visit ALL cells in a given grid: (experimented with my simulation apps) are summarized in the table below.
From my experiments in a 5X5 grid (setting the starting positions same for both methods in tkinter-pathBFS.py and in tkinter-pathDFS.py), there are some differences in number of moves required depending on the starting position in a same grid size. For example, BFS performs better if the starting position is near the top left corner (but not the very corner because for all corners, the results are same for both algos): 27 vs 29 moves required by DFS. But if the starting position is near the bottom right corner (but not the very corner), then DFS performs better than BFS: 45 vs 41 moves. As the number of grid gets larger the difference gets larger [see More Metrics below]. But, generally speaking, both BFS and DFS will require about the same number of moves to visit all cells. Using larger sizes of grids, we see the difference between BFS and DFS moves to explore all cells get larger in specific starting positions:
The following chart shows the number of moves required to explore full grids of different sizes using BFS and DFS algorithm at different starting positions.
Takeaway:
- BFS performed better (shorter bars) across all grid sizes when starting position was near top-left of the grid.
- DFS performed better (shorter bars) when starting position was near bottom-right of the grid.
- For other starting locations such as corners, both BFS and DFS required the same number of moves to explore all cells.
Run the simulations yourself
Below you can run the simulations that I wrote yourself right from here. Just click Run on the embedded widget. The starting position of the seeker will be randomly picked. Observe the different navigation techniques over different runs. Which one is performing better? Does it depend on the starting position or something else? The exploration space is same for both sims. The number of moves each took to explore the space is shown on each after completion. You can click Yes to run the sim again, or click No.
Navigaton sim using BFS:
Navigation sim using DFS:
About the simulation codes
I wrote two different scripts, one for simulating the navigation using BFS, another using DFS. The codes are written to be completly flexible to scale to any grid size with one line of change: the grid size and everything else will automatically redraw and resize accordingly.
I let the bot, the seeker (shown as a ladybug in the snapshot above), travel according to the algorithm from a given starting position. The starting position can be fixed or random for different experiments and measurements. BFS code uses a deque (no, not ‘dequeue’…that means to remove an element from a queue, but deque is a double-queue where we can remove items from ends efficiently) and the DFS code uses a stack.
In both versions, when the bot covers all the cells on the board (grid), the app stops and notifies the user. Then waits for user to respond to start a new simulation or not. The GUI uses tkinter library. It uses image rotation in the heading direction of seeker movement using the PIL (pillow) library.
The GUI provides a visual representation of the seeker’s journey, with visited cells highlighted to show the path taken. At the end of the game, the total number of moves made by the seeker is displayed for metric on the seeker’s efficiency.
The primary purpose of this script is to demonstrate a visual understanding of the algorithms. By visualizing the seeker’s path and the decision-making process, viewers can gain a deeper understanding of how they work and their advantages in navigating through simple and complex environments.
Calculating the number of vertices (plural of vertex), edges and complexity:
Understanding the vertices and edges helps us measure the complexity and efficiency of the algorithms. It is not needed for the code to perform the navigation but important for deciding on the best search/navigation algorithm based on the situation. So, here’s an example of how to derive vertices and edges in a very simple grid.
Supposed we have a 2×2 grid (each cell labeled for explanation) as follows:
For this scenario, the vertices are made of each cell meaning: A, B, C, D…so total 4 vertices (V=4).
To find the edges: We count only the unique edges. So, horizontal edges are: 
and vertical edges are: 
and there are these internal edges:
Between A and C (already counted as a vertical edge).
Between B and D (already counted as a vertical edge).
Between A and B (already counted as a horizontal edge).
Between C and D (already counted as a horizontal edge).
We don’t recount those, nor do we count the border lines (very top, very left, very right because there are no more cells or vertices shared). So, the unique edges are:
Horizontal edges: AB, CD
Vertical edges: AC, BD
Therefore, the total unique edges are:
Horizontal edges: 2
Vertical edges: 2
So, we have a total of 4 unique edges (E=4).
So, the time complexity for either BFS or DFS for this grid is 0(V+E) = O(4+4) = O(8)
For the simulation codes for either or both BFS and DFS (as shown in the animated snapshots above), contact me as follows.
I hope this was educational and interesting. You can get the full source code from my Patreon shop here (secure transaction).
In a future post, I plan to share a gamification of a path navigation script I’m working on that uses BFS algorithm with a twist.
▛
Interested in creating programmable, cool electronic gadgets? Give my newest book on Arduino a try: Hello Arduino! 
