Definitions

• $G=(V,E)$
• $V$ is a set of verticies (or nodes)
• $E$ is a set of edges (or links); also a pair of verticies
  • Notation for edge: $(u,v)$
• $|V|,|E|$ denotes the size of the sets

Example

• $V=\{1,2,3,4\}$
• $E=\{(1,2),(2,3),(3,4),(2,4)\}$

Representation

Adjacency List

$$ L[u]=\{v:(u,v)\in E\} $$

• $L$ is the adjacent list: an array of $|V|$ lists
• $L[u]$ contains all the vertices $v\in V$ that are connected to $u$
• Memory complexity: $O(|V|+|E|)$

Adjacency Matrix

$$ ⁍ $$

• $M$ is the adjacency matrix: a $|V| \times |V|$ matrix
• $M[u][v]$ is $1$ if there is an edge from vertex $u$ to vertex $v$, $0$ otherwise
• Memory complexity: $O(|V|^2)$

Properties & Features

<aside> 💡 Simple Graph: undrected, no multi-edge/loop Simple Directed Graph: directed, no multi-edge/loop

</aside>