En bitmatrise, viser om to “koordinater” har en kant mellom hverandre.
Effektivt om man vil slå opp raskt for å se om det eksisterer en kant. Ikke så bra for travasering (hvis det er få kanter i forhold til punkter).
Liste (eller tabell) med ut-naboer for hver node.
Kompakt; egnet til travasering; ikke så egnet til raske oppslag
Traversering generelt: Vi besøker noder, oppdager noder langs kanter og vedlikeholder en huskeliste.
Besøker nodene og noterer naboene til nodene, helt til lista er tom; da har vi besøkt alle vi kan.
Passer på om vi får overlappende naboer mellom forskjellige noder.
Så lenge vi bruker en FIFO-kø (dvs., BFS) så finner vi korteste vei; ellers risikerer vi å finne noder via omveier!
function bfs(G, s)
for vertex in G.V - {s}
vertex.color = WHITE
vertex.d = Inf
vertex.pi = nothing
s.color = GREY
s.d = 0
s.pi = nothing
Q = empty
enqueue(Q, s)
while Q != empty
u = dequeue(Q) #FIFO
for vertex in G.adj[u]
if vertex.color == WHITE
#Add vertex to queue
vertex.color = GREY
vertex.d = u.d + 1
enqueue(Q, vertex)
u.color = BLACK
DFS, flood-fill: Fyll rekursivt nord, øst, sør, vest
function dfs(G)
for vertex in G.v
u.color = WHITE
u.pi = nothing
time = 0 #global variabel, en counter
for vertex in G.v
if vertex.color == WHITE
dfs_visit(G, vertex)
function dfs_visit(G, vertex)
time = time + 1
vertex.d = time #Discover time
vertex.color = GREY
for v in G.adj[vertex]
if v.color == WHITE
v.pi = vertex
dfs_visit(G, v)
vertex.color = BLACK
time = time + 1
vertex.f = time #Finish time
Noder oppdages før og avsluttes etter sine etterkommere
Krever at grafen er en DAG! (Directed Asyclic Graph)