Depth-First Search and Breadth-First Search
GitHub Back to Homepage
Overview
DFS and BFS
Depth-First Search (DFS) and Breadth-First Search (BFS) are fundamental graph traversal algorithms used to explore nodes and edges in a graph or tree structure. DFS dives deep into a graph by exploring a node's neighbors recursively or via a stack until it reaches the deepest path or a goal, then backtracks. This approach is suitable for problems like maze solving or pathfinding in scenarios where exploring one path completely is advantageous. BFS, on the other hand, explores all neighbors of a node level by level using a queue, ensuring that the shortest path in an unweighted graph is found. BFS is widely used in shortest path problems and scenarios where breadth exploration is critical. Both algorithms are tested by solving a maze with random goal node.
Depth First Search
DFS example
The DFS (Depth-First Search) implementation explores the maze by iteratively using a stack to track the current path. It begins from a starting point and systematically explores all possible paths by moving in the directions north, south, east, and west. At each step, it pops the most recently added position (last-in, first-out behavior) from the stack and checks if it has reached the goal. If not visited, the position is marked as visited, and its valid neighbors (not out of bounds, walls, or already visited) are added to the stack for further exploration. As it progresses, visited cells are visually updated, and the maze state is displayed. If the goal is found, the shortest path is found and visualized from start to goal. This approach ensures that one complete path is explored before backtracking, highlighting the "depth-first" nature of the traversal.
Breadth-First Search
BFS Example
In this code, the BFS (Breadth-First Search) implementation explores the maze level by level, starting from the initial position. It uses a queue (deque) to store the paths being explored, ensuring the algorithm examines all possible moves from the current position before advancing deeper into the maze (first-in, first-out behavior). For each position, it checks if the goal is reached. If not, it generates new valid neighboring positions (not out of bounds, walls, or visited), appends them to the queue as extensions of the current path, and marks visited cells for visualization. The algorithm continues until it finds the goal, then reconstructs and visualizes the shortest path. BFS guarantees the shortest path in an unweighted maze since it systematically explores all paths of a given length before proceeding to longer ones.
Maze Visualization
The MazeVisualizer class provides a tool for dynamically visualizing the state of a maze as it is being solved. It uses matplotlib to display the maze as a grid, where different cell values are represented by specific colors defined in a discrete colormap. The color mapping ensures intuitive visual differentiation of maze components such as walls, paths, start, and goal. A method updates the visualization in real-time by clearing the previous state, rendering the current state of the maze, and pausing briefly for a specified interval to create an animated effect. This approach helps in observing the maze-solving process step by step, making the traversal algorithm's behavior easier to understand and debug.