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