Grafy a jejich implementace

Grafy:

Graf je reprezentován množinou vrcholů (uzlů) V, které mohou být spojeny určitým počtem hran H. Graf je poté definován jako G(V,H)

Neorientovaný graf: Hrany grafu nejsou orientované, tedy pokud vede hrana z uzli 1 do uzlu 5, vede i z uzlu 5 do uzlu 1 a platí tedy (u1, u2) = (u2, u1) Orientovaný graf: Hrany grafu jsou orientované (jednosměrné), tedy pokud vede hrana z uzli 1 do uzlu 5, nevede z uzlu 5 do uzlu 1 a platí tedy (u1, u2) != (u2, u1) Ohodnocený graf: Vednotlivé vrcholy či hrany mohou být ohodnoceny, graf tedy poté lze převést na množinu reálných čísel G(V, H) -> R

Implementace grafu:

1) Spojovými seznamy - seznam sousednosti

Máme seznam vrcholů a pro každý z nich máme seznam vrcholů, se kterými sousedí. Lze tak implementovat všechny 3 typy grafů (v obousměrných budou sousednosti v seznamech obou vrcholů sdílejících hranu, ohodnocení vrcholů je uloženo v seznamu vrcholů, ohodnocení hran je v seznamu sousednosti)

Problém metody je v složitosti hledání existence hrany, jelikož musíme procházet seznamy sousednost (Pro velké grafy pomalé, na druhou stranu pro řídké grafy méně pamětově náročné)

2) Maticí sousednosti

Stejný graf jako v 1)

Vytvoříme matici v*v prvků, kde v je počet vrcholů a hrany reprezentujeme jedničkami, zbytek matice jsou nuly.

Vidíme, že neorientovaný graf produkuje symetrickou matici, je tedy možné horní polovinu zanedbat a ušetřit tak paměť. Věškeré operace jsou O(1) (pokud použijeme 2rozměrné pole), paměťově je však tato implementace náročnější, jelikož alokujeme paměť i pro místa, kde hrany nejsou. Tato metoda je tedy vhodná pro časté vyhledávání ve větších grafech.

Ohodnocení lze provést uložením hodnoty místo jedniček, na diagonále lze ohodnotit vrcholy.