Welcome to DS&A 2

Throughout this course we'll be building parts of "Mappy" – an app like Google Maps or Apple Maps that people can use to find directions on their smartphones.

We'll start this course with some advanced use cases of graph data structures; remember, a graph represents a set of nodes and the edges between them.

In code, a graph can be represented with an adjacency list. For example, the graph shown above can be expressed like this:

Complete the __init__ and add_edge methods.

__init__(self) -> None

The constructor should create an empty dictionary called graph as a data member.

add_edge(self, u: str, v: str) -> None

add_edge takes two nodes as inputs, and should add an edge to the adjacency list (the dictionary).

The dictionary maps nodes to a set of all other nodes they share an edge with. For example, in JSON form it would look like this:

{
  "0": [1, 4],
  "1": [0, 2, 3, 4],
  "2": [1, 3],
  "3": [1, 2, 4],
  "4": [0, 1, 3]
}

Use these steps:

1. If node u is already a key in the dictionary, add v to u's set.
2. Otherwise, create a new set for u that contains v.
3. Repeat steps 1 & 2, but swap u and v.