Reprezentado de grafeo

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

La artikolo estas parto de serio pri grafeoteorio.

Plej gravaj terminoj grafeo arbo subgrafeo ciklo kliko grado de vertico grado de grafeo Elektitaj klasoj de grafeoj plena grafeo plena dukolora grafeo kohera grafeo arbo grafeo dudividebla Fenda grafeo regula grafeo grafeo de Euler grafeo de Hamilton grafeo senrelifa pli... Grafeaj algoritmoj A* Bellman-Ford Dijkstry Fleury Floyd-Warshall Johnson Kruskal Prim traserĉado de grafeo – en larĝeco – en profundo plej proksima najbaro Problemoj prezentataj kiel grafeaj problemo de vojaĝisto problemo de ĉina leteristo problemo de marŝrutigado problemo de kunigado de geedzoj Aliaj kodo de Gray diagramo de Hasse kodo de Prüfer Reprezentado de grafeo Glosaro de grafeoteorio

Grafea datuma strukturo povas ankaŭ asocii etikedon al eĝoj. La etikedo povas havi simbolan aŭ nombran valoron (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