Graph

Graphs are usually stored in two ways - in a metric or in a set of nodes where each item has a references to a node it is connected with. Nice summary is in this video.

Adjacency Matrix

Directed graph.

For undirected graph, we can keep only one side of matrix (upper or lower).

Directed weighted graph.

Adjacency List

Directed graph (we can store incoming or out-coming edges).

Undirected graph, each edge is stored twice.

Adjacency matrix is bad for sparse graphs and good for dense graphs. The opposite of adjacency list.