Zusammenfassung der Ressource
Grafy III.
- Určení minimální kostry
- Jarník-Prim
- Algoritmus
- Přidej všechny uzly do fronty a nastav jim
nekonečnou vzdálenost od podstromu
- Kořen má vzdálenost nula a NIL předchůdce
- Dokud fronta není prázdná
- Vyber nejbližší uzel a vyjmi ho z fronty
- Pro všechny jeho sousedy zkontroluj a případně nastav
novou minimální vzdálenost a nového předchůdce
- Vypiš kostru po předchůdcích pro každý uzel
- Vlastnosti
- Maximálně |V(G)| kroků
- Výsledkem je strom protože se vždy přidávají jen listy.
Navíc má právě |V(G)| uzlů = jedná se o minimální kostru
- Složitost O(n^2 + m)
- S Fibonacciho haldou lze až O(m + log(n)n)
- Popis
- Buduje podstrom od náhodného kořene
- Rozšířuje podstrom přidáváním uzlů, které mají k
aktuálnímu podstormu nejkratší vzdálenost
- Kruskal ("greedy")
- Popis
- Každý uzel je podstromem
- Prochází hrany uspořádané podle vah a
rozšiřuje podstromy aniž by vytvářel cykly
- Hrany které vytváří cyklus přeskakuje
- Algoritmus
- Uspořádej hrany v rostoucí posloupnosti podle vah
- Projdi každou hranu v posloupnosti
- Pokud počáteční a koncový uzel není součástí
stejného podstromu, přidej hranu a spoj oba podstromy
- Vlastnosti
- Právě |E(G)| iterací
- Může být zastaven dříve zařážkou po přidání |V(G)| - 1 hran
- Union-find problem
- Algoritmus používá dotaz na náležitost uzlu
podstormu (FIND) a sjednocení podstromů (UNION)
- Prosté řešení
- Každý podstrom je spojový seznam
- Každý prvek obsahuje také odkaz
na první prvek (reprezentant)
- O(FIND) = 1
- O(UNION) = n
- Nutno spojit seznamy
- Pro každý uzel připojovaného
seznamu přepsat reprezentanta
- Lze vylepšit připojováním kratšiho ze
seznamů - nutné udržovat délku
seznamu u reprezentanta
- O(|E(G)|.log|V(G)| + |V(G)|^2)
- Vylepšená reprezentace
- Les kořenových stromů
- Každý prvek obsahuje jen odkaz na rodiče,
kořen je reprezentant a sám sobě rodičem
- O(UNION) = 1
- Připojení rodiče jako potomka
- O(FIND) = n
- Vylepšíme heuristikami
- Zkracujeme cestu - při FIND
přepojíme rodiče o úroveň výš -
zkracujeme hloubku
- Vyvžujeme hodnost - při UNION připojíme
podstrom s menším počtem uzlů (na začátku
hodnost 0, při spojení +1)
- O(|E(G)|.log|V(G)|)
- Borůvka
- Popis
- Rozdělí graf do komponent a v cyklech přidává
každé komponentě hranu s nejnižší vahou
- Algoritmus
- Vytvoř K který obsahuje všechny uzly bez hran
- Graf K obsahuje právě E(G) komponent
- Dokud K obsahuje alespoň dvě komponenty
- Pro každou komponentu přidej hranu s nejnižší vahou
- Rozpad lesa na komponenty pomocí DFS
- Každý uzel má přiřazené číslo komponenty
- Pro každou hranu zjistíme, do kterých komponent patří
- Pro každou komponentu uložíme minimální hranu
- Po projítí všech hran ke každé komponentě
přidáme novou minimální hranu
- Vlastnosti
- Po k iteracích všechny komponenty
grafu mají alespoň 2^k uzlů
- Složitost O(|E(G)|.log|V(G)|)
- Určení komponent grafu
- Kosaraju-Sharir
- Popis
- Hledání silných komponent grafu
- Využívá rekurzivní DFS a transponovaného
grafu k nalezení uzavřených komponent
- Algoritmus
- Přes DFS projdi celý graf
- V okamžiku uzavření uzel přidej do zásobníku
- Jakmile zásobník obsahuje všechny vrcholy (všechny uzly jsou closed)
- Obrať orientaci všech hran - vytvoř transponovaný graf
- Dokud zásobník není prázdný
- Vyjmi uzel
- Pokud je unvisited zavolej DFS nad transponovaným grafem
- Navštívené uzly v DFS tvoří komponentu
- Vlastnosti
- Adjacency matrix - max složitost O(|V|^2)
- DFS dvakrát nad celým grafem
- Adjacency list - průměrná složitost o(|V|+|E|)
- Tarjan
- Popis
- Používá upravenou verzi DFS a počítá index prvků
- Komponentu uzavírá pokud ví, že z uzlu
není dosažitelný prvek s nižším indexem
- Proto stačí jen jeden průchod grafem
- Při návratu z rekurze kontroluje, jestli index potomka je
nižší než index rodiče a pamatuje si nejnižší dosažitelný index
- Algoritmus
- Zavolej DFS na všechny neobjevené uzly
- Při navštívení nového uzlu přiřaď uzlu index, přidej
ho do zásobníku a zvyš počítadlo indexu o 1
- Před uzavřením uzlu zkontroluj, jestli jeho u.minindex == u.index
- Pokud ano, vyprázdňuj zásobník dokud
nenarazíš na kořen (u) jako novou
komponentu do seznamu komponent
- Tj. jestli jsme v kořenu komponenty
- DFS strom se dále nevětví => zkontrolujeme
minimální dosažitelný prvek
- Tj. po návratu z rekurze
- nebo při odhalení visited potomka, který
ještě není součástí uzavřené komponenty
- Pokud už je v uzavřené
komponentě, je dosažitelný jen
jednosměrně a nemá cenu ho řešit
- Přiřadíme u.minindex = min(u.index,
s.minindex) kde s je potomek
- Vlastnosti
- Složitost stejná jako Kosaraju-Sharir
- Ale jen jeden průchod grafem - je rychlejší
- Speciální tahy v grafu
- Eulerův tah
- Tah, který projde všechny uzly a hrany grafu,
a každou hranu navštíví právě jednou
- Podmínky
- Graf je souvislý
- Má právě 0 vrcholů lichého stupně
- tzv. Eulerian Tour
- Pokud Eulerův tah končí a začíná ve stejném uzlu
- Nebo má právě 2 vrcholy lichého stupně
- Pokud Eulerův tah končí a začíná v různých uzlech
- Jak nalézt Eulerův tah
- Popis
- Začíná se v uzlu lichého stupně pokud existuje, jinak libovolně
- Je rekurzivní
- Vhodné nejprve otestovat stupně uzlů a souvislost přes DFS
- Algoritmus
- Pro každého potomka uzlu
- Smaž hranu edge(v,u)
- Přidej do zásobníku hranu edge(v,u)
- Zavolej rekurzi na potomka (u)
- Rekurze se vrací pokud už neexistuje
potomek (všechny hrany smazány)
- Vlastnosti
- Jeden průchod grafem
- Adjacency list - průměrná složitost o(|V|+|E|)
- Adjacency matrix - maximální složitost O(|V|^2)
- Hamiltonovská cesta
- Cesta, která navštíví každý uzel právě jednou
- Nemusí projít všechny hrany
- NPC problém