Adjazenzmatrix

Einfache Sprache

Def. Adjazenzmatrix

Die Adjazenzmatrix zu Graph $G = (V, E)$ mit $V = \{v_0 ,\ldots , v_{n−1}\}$ ist eine $(n × n)$-Matrix mit

$$A[i, j] =\begin{cases} 1 &\text{falls } \{v_i , v_j \} \in E \text{ bzw. } (v_i , v_j ) \\ 0 & \text{sonst}\end{cases}$$

Der Speicherplatzbedarf ist $\mathcal O(|V|^2)$. Test ob $\{v_i,v_j\}\in E$ geht in $\mathcal O(|V|)$.