Graphs

Overview

There are two standard ways of representing graphs in memory: adjacency-list representations and adjacency-matrix representations.

Adjacency-List

Let $G=⟨V,E⟩$ be a graph. An adjacency-list representation of $G$ has an array of size $|V|$. Given $v\in V$, the index corresponding to $v$ contains a linked list containing all adjacent vertices.

Adjacency-Matrix

Let $G=⟨V,E⟩$ be a graph. An adjacency-matrix representation of $G$ is a $|V|\times |V|$ matrix $A=(a_{ij})$ such that