Graphs

Graphs are data structures that represent nodes/items (vertices), and their connections (edges).

Directed-ness

Graphs can be directed: The edges of the graph specify a connection from one node to another (in a single direction). Undirected graphs have edges that are (implicitly) bi-directional.

graph TB;
  subgraph Directed
    a-->b & c;
    b-->d;
    c-->d & e;
  end
  subgraph Undirected
    1---2 & 3;
    2---4;
    3---4 & 5;
  end

Cycles

Graph can be A/Cyclic: Acyclic graphs have connections that do not form any loops (cycles), whereas cyclic graphs do.

graph TB;
  subgraph Acyclic
    a-->b & c;
    b-->d;
    c-->d & e;
  end
  subgraph Cyclic
    1-->2 & 3;
    2-->4;
    3-->4 & 5;
    4-->2;
    5-->1;
  end

Implementations

Graphs are often implemented in one of two ways.

1. A set of nodes/vertices, with a separate map containing the edges for each node (called an “Adjacency List”).
2. A node structure where the nodes themselves store a list of pointers to the other nodes they are connected to.

To-do

• Graph
  • Trees
    • Tries
    • Binary Tree
    • Red-Black Tree
    • Radix-trees
    • …