Welcome to DS&A 2
Welcome to Data Structures and Algorithms, Part 2! In this course, we'll cover more of the advanced data structures and algorithms that we didn't have a chance to address in Part 1.
Mappy
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.
Graph Review
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:
| 0 | connects with | 1 | 4 | ||
| 1 | connects with | 0 | 2 | 3 | 4 |
| 2 | connects with | 1 | 3 | ||
| 3 | connects with | 1 | 2 | 4 | |
| 4 | connects with | 0 | 1 | 3 |
Assignment
Complete the __init__ and add_edge methods.
__init__(self)
The constructor should create an empty dictionary called graph as a data member.
add_edge(self, u, v)
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: