Solve the Maze Using a Graph-Based Approach
00:00 Solve the Maze Using a Graph-Based Approach. At this point, you can represent the maze and its solution in an object-oriented form. You can visualize them, as well as serialize the maze using a custom binary file format.
00:15 Now it’s time to convert your maze to a graph and let Python find the shortest path from the entrance to the exit. By the end of this part of the course, you’ll have a command-line program for solving and visualizing mazes loaded from a specified file.
00:32 Graphs are an important data structure in theoretical computer science, which often come up during code interviews. While you may use them sparingly in your day-to-day programming practice, graphs can help solve a variety of problems, such as finding your way out of a maze.
00:50 A graph is a set of nodes and the edges between them. Because nodes have no inherent location in space, when you convert the maze into a graph form, you will lose some information about its geometry. Later, you’ll add weights to the edges to represent the cost of traversing each connection between two nodes.
As a rule of thumb, you should avoid specifying concrete dependency versions directly in the
pyproject.toml file, particularly when you intend to use your package as a reusable library in other projects that might depend on different NetworkX versions.
However, it’s always a good idea to pin dependency versions in a
requirements.txt file to ensure reproducible builds. Next, reinstall your package in your virtual environment using the editable mode once more so that the
networkx package becomes available for importing.
Before moving on, you create your final Python package in your project with the
solver placeholder modules. The
converter module will contain a few functions for turning your maze into a graph, while the
solver module will use those functions as glue code to wrap NetworkX’s algorithms and solve your maze.
Become a Member to join the conversation.