Reprezentado de grafeo

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo
La artikolo estas parto de serio pri grafeteorio.




Plej gravaj terminoj
grafeo
arbo
subgrafeo
ciklo
kliko
grado de vertico
grado de grafeo


Elektitaj klasoj de grafejo
plena grafeo
plena dukolora grafeo
kohera grafeo
arbo
grafeo dudivdebla
Fenda grafeo
regula grafeo
grafeo de Euler
grafeo de Hamilton
grafeo senrelifa


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


Alijaj
kodo de Gray
diagramo de Hasse
kodo de Prüfer


Reprezentado de grafeo Glosaro de grafeteorio


vidi  diskuti  redakti

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[redakti | redakti fonton]

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