# 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:
• 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
• 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

## 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"] = []