Graph - jaredgorski.org

Graph

data structures

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