What is a Graph?

A graph is a data structure that models a set of things and the connections between them. The things are called vertices (or nodes) and the connections are called edges.

Graphs are everywhere. Social networks are graphs (people are vertices, friendships are edges). Road maps are graphs (intersections are vertices, streets are edges). The internet, dependency trees, and game maps are all graphs.

In this course we focus on an undirected graph: if an edge connects u and v, then v is also connected to u. There is no direction. We will use integers as the vertex keys to keep things simple.

Internally we will store the graph as an adjacency list: a map from each vertex to the list of its neighbors. This makes looking up a vertex's neighbors a single map access, which is what most graph algorithms need.

The operations we will build on our Graph class are:

1. addVertex: Add a new vertex with no edges yet.
2. addEdge: Connect two vertices.
3. hasEdge: Check whether two vertices are connected.
4. getNeighbors: Get the list of a vertex's neighbors.
5. removeEdge: Disconnect two vertices.
6. size: Count how many vertices the graph has.

Let's build a Graph class!