Graphs

Graphs are collections of nodes with edges connecting them. In a directed graph, the edges have directions (like an edge might go from $a$ to $b$ but not from $b$ to $a$), and in an undirected graph, they don't (an edge connecting $a$ to $b$ also connects $b$ to $a$).

Graphs are called connected if there is a path of edges connecting all nodes. A directed graph with no cycles (no directed paths that can lead in a circle) is called acyclic. A graph is weighted if each edge has an associated weight.

There are two main ways to represent a graph programmatically.

Adjacency-list representation

For a graph $G\; =\; (V,\; E)$, an adjacency-list representation starts with an array of $|V|$ pointers, where $|V|$ is the number of vertices in the graph. Each pointer in the array points to a linked list, where each node in the linked list specifies another vertex in the graph. The presence (or absence) of a node indicates an edge from the node whose adjacency list list it is to the vertex specified by the node.

For example, in the $uth$ spot in the array corresponds to the edges leaving the vertex $u$. In $u$'s adjacency list, the presence of a node with the value $v$ indicates that in our graph, there is an edge from $u$ to $v$.

For directed graphs, a $v$ node in $u$'s adjacency list specifies an edge from $u$ to $v$, which doesn't imply an edge from $v$ to $u$.

This adjacency-list schema uses $O(V\; +\; E)$ memory, where $V$ is the number of vertices and $E$ is the number of edges: an array of $V$ elements and then $E$ total linked list nodes. Iterating over each edge takes $O(V\; +\; E)$ time, for the same reason, although since worst-case, there are asymptotically more edges than nodes (in a fully connected graph (the worst-case), there are $n(n-1)⁄$₂ edges for $n$ nodes), we can just say iterating over each node is $O(E)$.

Adjacency-matrix representation

The adjacency-matrix representation for a graph $G\; =\; (V,\; E)$ uses a $|V|\; \times \; |V|$ matrix $A$ where

$a$_{i, j} = 1 if (i, j) ∈ E, otherwise 0

This approach requires $O(V2)$ memory, but is irrespective of the number of edges in the graph. Iterating over each edge takes $O(V2)$ time.

Comparison

Generally, the adjacency-list approach is better for sparsely connected graphs; where , and the adjacency-matrix approach is better for densely connected graphs where $|E|$ approaches $|V|2$. Also, in the adjacency-list approach, looking for the presence of an edge requires indexing into the array and then searching the linked list (worst case $O(E)$), whereas the adjacency-matrix approach takes constant time for edge lookup.