Grafrepresentasjon

Bruker Nabomatriser for tette grafer (mange kanter) Bruker Nabolister

Begreper

Nabomatriser

Dersom det går en kant fra $i$ til $j$, vil $A_{ij}=1$ og ellers $A_{ij}=0$ Plass: $\Theta (|V{|}^2)$ Tid for å sjekke en kant: $\Theta (1)$

Link to original

---

Nabolister

En liste med lister, der indeks $i$ i listen har en liste over alle noder som node i har en kant til Plass: $\Theta (V+E)$ Tid for å sjekke en kant: $O(V)$

Link to original

Bruksområder

Når bruker vi nabomatriser vs nabolister?

	Nabomatriser	Nabolister
Pros	Mange kanter gjør det lett å slå opp i	Lett å traverse, og bruker lite plass
Cons	Tar opp V² plass uansett	Tar lengre tid å slå opp siden den må traversere