Learn

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.

Sign up to start coding

Mini Info Outline Icon
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?