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 $a_{ij}=\{\begin{array}{ll}1& \text{if }⟨i,j⟩\in E\\ 0& \text{otherwise}\end{array}$

Bibliography

• Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).