Skip to content

2.2 Reprezentace grafů

RAM a složitost

Definice 2.6 (Výpočetní model RAM)

Výpočetní model RAM

Random Access Machine

  • Paměť RAMu tvoří pole celočíselných paměťových buněk adresovatelných celými čísly.
  • Program je konečná posloupnost sekvenčně prováděných instrukcí dvou typů:
    aritmeticko-logických a řídicích.
  • Aritmeticko-logické instrukce mají obvykle dva vstupní argumenty a jeden výstupní argument. Argument může být:
    • přímá konstanta (s výjimkou výstupního argumentu),
    • přímo adresovaná paměťová buňka (adresa je přímo zadána),
    • nepřímo adresovaná paměťová buňka (její adresa je uložena v přímo adresované buňce).
  • Řídicí instrukce jsou skoky (na konkrétní instrukci programu), podmíněné skoky (například když se dva argumenty instrukce rovnají) a instrukci zastavení programu.
  • Na začátku výpočtu obsahuje paměť v určených buňkách vstup a obsah ostatních buněk je nedefinován.
  • Potom je program sekvenčně prováděn, instrukce za instrukcí.
  • Procesor v každém kroku provede právě jednu instrukci.
  • Po zastavení programu je obsah paměti v určených buňkách interpretován jako výstup programu

Definice 2.7 (Složitost programu)

Složitost programu

  • Velikost vstupu je počet paměťových buněk, které vstup zabírá.
  • Časová složitost programu (v nejhorším případě) pro vstup velikosti \(N\) je maximum z počtu vykonaných instrukcí přes všechny možné (povolené) vstupy velikosti nejvýše \(N\).
  • Paměťová složitost programu (v nejhorším případě) pro vstup velikosti \(N\) je maximum z počtu použitých paměťových buněk přes všechny možné (povolené) vstupy velikosti nejvýše \(N\).

Reprezentace grafu

Jak reprezentovat (neorientované) grafy v paměti počítače?

  • Matice sousednosti
  • Seznam sousedů

Definice 2.8 (Matice sousednosti)

Matice sousednosti

Nechť \(G = (V, E)\) je graf s \(V = \{v_{1}, v_{2}, ... , v_{n}\}\).

Matice sousednosti grafu \(G\) je čtvercová matice \(A_{G} = (a_{i,j} )^{n}_{i,j=1}\)

\[ a_{i,j} = \begin{cases} 1 & \text{když } \{v_{i}, v_{j}\} \in E, \\ 0 & \text{jinak} \\ \end{cases} \]

Pozorování

  • \(A_{G}\) je symetrická matice
  • Paměťová náročnost reprezentace: \(O(n^{2})\)

Definice 2.9 (Seznam sousedů)

Seznam sousedů

Pro každý vrchol v grafu \(G = (V, E)\) uchováváme seznam jeho sousedů (např. spojový seznam).

Paměťová složitost: \(|V|\) začátků seznamů a dohromady \(2|E|\) prvků v seznamech (každá hrana znamená dva výskyty).

Pozorování

Celkem tedy paměťová složitost: \(O(n + m)\).

Orientovaný graf

Orientované grafy reprezentujeme ve stejných strukturách jako neorientované grafy:

  • maticí sousednosti
  • seznamem sousedů

pouze místo seznamu sousedů říkáme seznam následníků:

Analýza časové složitosti BFS

Věta 2.1 (O časové složitosti algoritmu BFS_graf)

Věta o časové složitosti BFS

Algoritmus BFS_graf(\(G\)) má při reprezentaci grafu \(G\) seznamem sousedů časovou složitost \(O(|V| + |E|)\).

Důkaz Věty 2.1
  1. V globálním seznamu stavu vrcholů se každý vrchol vyjme nanejvýš jednou a poté se pustí BFS z něho.
  2. Každý vrchol je přidán do fronty \(Q\) nejvýše jednou.
  3. V každé iteraci cyklu \((9)\)–\((16)\) je jeden vrchol odebrán z fronty, tento cyklus má tedy nejvýše \(|V|\) iterací.
  4. Celkový počet iterací cyklu \((11)\)–\((15)\) je nejvýše dvakrát tolik, kolik je v grafu hran
    (neboť pro každý vrchol procházíme jen hrany a vrcholy v jeho komponentě souvislosti).
  5. Celková časová složitost je tedy \(O(|V| + |E|)\).