Reprezentado de grafeo

Reprezentado de grafeo estas datuma strukturo en memoro de komputilo, kiu reprezentas ideon de matematika grafeo. Datuma strukturo konsistas el finita (kaj eventuale ŝanĝebla) aroj de ordigitaj paroj de verticoj. La paroj estas nomataj eĝoj.

Grafea datuma strukturo povas ankaŭ asocii etikedon al eĝoj. La etikedon povas havi simbolikan valoron aŭ nombran (kosto, distanco, ktp.)

Reprezentado

La plej popularaj manieroj de reprezentado de grafeo estas:

1. apudeca listo
2. apudeca matrico
3. incideca listo
4. incideca matrico

	apudeca listo	incideca listo	apudeca matrico	incideca matrico
Memoro	$O(|V|+|E|)$	$O(|V|+|E|)$	$O(|V|^{2})$	$O(|V|\cdot |E|)$
Aldonado de vertico	$O(1)$	$O(1)$	$O(|V|^{2})$	$O(|V|\cdot |E|)$
Aldonado de eĝo	$O(1)$	$O(1)$	$O(1)$	$O(|V|\cdot |E|)$
Forigado de vertico	$O(|E|)$	$O(|E|)$	$O(|V|^{2})$	$O(|V|\cdot |E|)$
Forigado de eĝo	$O(|E|)$	$O(|E|)$	$O(1)$	$O(|V|\cdot |E|)$
Serĉmendo: Ĉu verticoj u, v apuda? (Supozante ke la pozicioj por u, v en la memoro estas konata)	$O(|V|)$	$O(|E|)$	$O(1)$	$O(|E|)$
Rimarkoj:	Kiam okazas forigado ed eĝo aŭ vertico, ankaŭ necesas trovi ĉiuj verticoj aŭ gexoj