# Graph

“A graph models a set of connections.”^{[1]} It’s a mathematical data structure used to model 1-to-1 relationships between components of the graph.

Graphs are made up of **nodes** and **edges**:

**nodes**:- AKA “vertices” or “points”
- connected by “edges”
- nodes that are directly connected are called “neighbors”

**edges**:- AKA “links” or “lines”
- connect “nodes” to each other

There are multiple types of graphs:

**undirected**:- edges connect vertices “symmetrically”:
- any vertex can connect to any other vertex equally

- groups of connected vertices within an undirected graph are called “connected components” or “components”
- undirected graphs can be thought of as directed graphs where each connection is 2-way
- e.g., a graph of familial relationships

- edges connect vertices “symmetrically”:
**directed**:- edges connect vertices “asymmetrically”:
- relationships between vertices can only be established depending on which vertex is establishing the relationship – relationships in graphs
*aren’t necessarily reciprocal* - e.g., a graph of people who owe other people money

- relationships between vertices can only be established depending on which vertex is establishing the relationship – relationships in graphs

- edges connect vertices “asymmetrically”:

## Implementation

Graphs are implemented using Hash tables. Each key in the hash table is assigned a list of its direct neighbors.

Here’s a python implementation:

```
graph = {}
graph["chicago"] = ["detroit", "st. louis", "minneapolis"]
graph["detroit"] = ["chicago", "toronto"]
graph["st. louis"] = ["chicago, "nashville", "tulsa"]
graph["nashville"] = ["st. louis", "tulsa", "charlotte"]
graph["honolulu"] = []
```