Grafy a jejich implementace
m (kategorizace) |
|||
| (Není zobrazeno 8 mezilehlých verzí od 1 uživatele.) | |||
| Řádka 1: | Řádka 1: | ||
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) | 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 | + | * '''Neorientovaný graf''': Hrany grafu nejsou orientované, tedy pokud vede hrana z uzlu 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 | + | * '''Orientovaný graf''': Hrany grafu jsou orientované (jednosměrné), tedy pokud vede hrana z uzlu 1 do uzlu 5, nevede automaticky zpět z uzlu 5 do uzlu 1 a platí tedy (u1, u2) != (u2, u1) |
| − | * '''Ohodnocený graf''': | + | |
| + | |||
| + | * '''Ohodnocený graf''': Každá hrana má přižezenou svoji hodnotu (číslo). Tyto hodnoty pak udávají například délku hrany, propustnost nebo třeba cenu za přechod po dané hraně. | ||
| + | * '''Neohodnocený graf''': Všechhny hrany grafu jsou si rovny (v podstatě jsou všechny ohodnoceny stejným číslem), takže nemá smysl uchocácat informaci o jejich ohodnocení. | ||
== Implementace grafu pomocí spojového seznamu (seznam sousednosti) == | == Implementace grafu pomocí spojového seznamu (seznam sousednosti) == | ||
| + | |||
| + | [[Soubor:Graf-spojovy-seznam.jpg|500px]] | ||
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) | 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é) | 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é) | ||
| − | |||
| − | |||
== Implementace grafu pomocí matice sousednosti == | == Implementace grafu pomocí matice sousednosti == | ||
| − | |||
| − | |||
Stejný graf jako v předchozím případě | Stejný graf jako v předchozím případě | ||
| + | |||
| + | [[Soubor:Graf-seznam-sousednosti.jpg]] | ||
Vytvoříme matici v*v prvků, kde v je počet vrcholů a hrany reprezentujeme jedničkami, zbytek matice jsou nuly. | Vytvoříme matici v*v prvků, kde v je počet vrcholů a hrany reprezentujeme jedničkami, zbytek matice jsou nuly. | ||
| Řádka 25: | Řádka 28: | ||
Ohodnocení lze provést uložením hodnoty místo jedniček, na diagonále lze ohodnotit vrcholy. | Ohodnocení lze provést uložením hodnoty místo jedniček, na diagonále lze ohodnotit vrcholy. | ||
| + | |||
| + | |||
| + | // co třeba hledání kostry grafu a podobný vylomeniny? | ||
| + | |||
| + | {{fav-kiv-bzinf}} | ||
| + | [[Kategorie:fav-kiv-bzinf]] | ||
Aktuální verze z 20. 2. 2014, 06:35
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 uzlu 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 uzlu 1 do uzlu 5, nevede automaticky zpět z uzlu 5 do uzlu 1 a platí tedy (u1, u2) != (u2, u1)
- Ohodnocený graf: Každá hrana má přižezenou svoji hodnotu (číslo). Tyto hodnoty pak udávají například délku hrany, propustnost nebo třeba cenu za přechod po dané hraně.
- Neohodnocený graf: Všechhny hrany grafu jsou si rovny (v podstatě jsou všechny ohodnoceny stejným číslem), takže nemá smysl uchocácat informaci o jejich ohodnocení.
[editovat] Implementace grafu pomocí spojového seznamu (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é)
[editovat] Implementace grafu pomocí matice sousednosti
Stejný graf jako v předchozím případě
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.
// co třeba hledání kostry grafu a podobný vylomeniny?
