Path: A connected list of vertices

• Path Length: Number of edges (not vertices!) in a path
• Simple Path: No repeated vertex or edge
• Cycle: A path where start vertex = end vertex
• Simple Cycle: Cycle without repeated edge or vertex (except for the start & end)

Graph Data Structures

Graph $G=(V,E)$ | $V=\{v_1, \dots, v_n\}$ | $n=|V|,m=|E|$

Adjacency Matrix

• Rows: from, Cols: to
• matrix[r, c] = 1 means there is an edge from r to c
• Symmetric for undirected graph (but symmetric doesn’t imply it’s undirected)

Complexity

• Space: θ(n²)
• Edge Query: θ(1)
• Neighbour Query: θ(n)

$$ \begin{matrix}
& a & b & c & d & e \\ \hline a |& 0 & 1 & 1 & 0 & 0 \\ b |& 0 & 0 & 0 & 1 & 1 \\ c |& 0 & 0 & 0 & 0 & 0 \\ d |& 0 & 0 & 0 & 0 & 0\\ e |& 0 & 0 & 0 & 0 & 0\\ \end{matrix} $$

Adjacency List (Sparse Matrix)

• Array (size n) of LinkedLists of edges (e.g. [a: [b → c → d], b: [a → c], …])

Complexity

• Space: θ(n + m)