In this lesson, we’ll build a robust implementation of the graph data structure. With just two classes, Vertex
and Graph
, we can implement a variety of graphs that satisfy the requirements of many algorithms.
Let’s detail the functionality we require from these classes:
Vertex
stores some data.Vertex
stores the edges to connected vertices and their weight.Vertex
can add a new edge to its collection.Graph
stores all the vertices.Graph
knows if it is directed or undirected.Graph
can add a new vertex to its collection.Graph
can add a new edge between stored vertices.Graph
can tell whether a path exists between stored vertices.
Since we’re dealing with multiple classes, we’ll use multiple files for this implementation. To keep the concepts grounded in a real-world application, we’ll build up a transportation network of railroads and train stations as we go.
Instructions
The files vertex.py and graph.py contain the classes we’ll be building through the lesson. script.py has some utility code to build a random graph and print its vertices and edges to the console.
Run that code a few times to see different graphs printed and continue when you’re ready.