Adjazenzliste

Einfache Sprache

Def. Adjazenzliste

Sei $G = (V, E)$ ein Graph. Für jeden Knoten $v \in V$ wird

$$Adj(v) = \{u \in V |\{v, u\} \in E\}$$

als Liste abgespeichert. Der Speicherplatzbedarf ist $\mathcal O(|V|+|E|)$. Test ob $\{v_i,v_j\}\in E$ geht in $\mathcal O(|V|)$.