Ukázka grafu
Graf je trojice G = <V, E, ε>, kde V je množina vrcholů, E je množina hran a zobrazení ε : E → {{u,v}| u, v ∈ V}
Předpokládáme, že množina vrcholů V = {0, 1, ..., n-1}
Graf můžeme reprezentovat pomocí seznamu sousedů nebo pomocí matice sousednosti.
Mějme pole adj o velikosti ne, kde prvek adj[u] je seznam vrcholů, obsahující prácě vrcholy z množiny {v |(u,v) ∈ V}. Jedná se o vhodnou reprezentaci pro řídké grafy (obzvláště pro ty kdy počet hran je menší než druhá mocnina n). Nevýhodou je nemožnost v konstantním čase provádět operaci vyhledávání hrany.
Matice sousednosti grafu G je matice A = (aij)n x n, kde aij = 1, pokud (i, j) ∈ E, a aij = 0, pokud (i, j) ∉ E
Takovouto matici můžeme v počítači chápat jako dvourozměrné pole
Matice je vhodná pro grafy, kde počet hran je velký. Výhodou je možnost provádět operace vyhledávání hrany v konstantním čase.
Je dobré si uvědoit, že matice sousednosti pro neorientovaný gram je symetrická podle hlavní diagonály.
Procházení grafu je výpočetní problém, který spočívá v navštívení všech vrcholů grafu. Existují dvě základní strategie procházení grafu: průchod do šířky a průchod do hloubky.
Alternativním problémem je průchod grafem z daného počátečního vrcholu. Chceme navštívit všechny vrcholy dosažitelné vrcholy právě jednou.
bfs(g:graph, s:int):
vytvoř pole X délky len(g.adj) s hodnotami false, g.adj je pole seznamů grafu g reprezentovaný pomocí seznamů sousedů
vytvoř frontu Q
slož s do Q
while Q není prázdná:
odeber z Q vrchol u
pro každý vrchol w ze seznamu g.adj[u], pro který X[w] == false:
X[w] = true
vlož w do Q
dfs(g:graph, s:int):
vytvoř pole X délky len(g.adj) s hodnotami false, g.adj je pole seznamů grafu g reprezentovaný pomocí seznamů sousedů
vytvoř zásobník S
vlož t do S
while S není prázdný:
odeber z S vrchol u
pro každý vrchol w ze seznamu g.adj[u], pro který X[w] == false:
X[w] = true
vlož w do S
Funguje na stejném principu jako klasická fronta, ale navíc ukládá data ve dvojici: priorita, data. Pokud budeme brát prioritu jako klíče a povolíme opakování kléčů, pak můžeme využít struktury vyhledávacích stromů.
Ukázka běhu s vysvětlením například tímto videem.
dijkstra(g:graph, s:int) -> []:real:
vytvoř pole X a Y délek len(g.adj), všechny prvky nastav na false
vytvoř D délky lne(g.adj), nastav všechny prvky na nekonečno
vytvoř prioritní fromtu PQ
vlož (s, 0) do PQ
dokud PQ není prázdná:
odeber minimum (u, d) z PQ
nastav Y[u] na true a D[u] na d
pro každý vrchol z v seznamu g.adj[u], pro který je Y[z] == false:
pokud X[z] == false:
X[z] = true
vlož (z, d + g.c(u, z)) do PQ
nebo:
změň prioritu vrcholu z na d + g.c(u, z)
return D