STROMOVE ALGORITMY Prohledavani do sirky (level-order) Po vodorovnejch carach vlož do fronty kořen opakuj, dokud není fronta prázdná 1. vyber uzel z fronty a zpracuj jej 2. vlož do fronty levého následníka 3. vlož do fronty pravého následníka Prohledavani do hloubky (pre-order) De dohloubky kam az to de a pak se vraci – vlož kořen na zásobník – dokud není zásobník prázdný, opakuj
• vyber uzel z vrcholu zásobníku a zpracuj jej • vlož na zásobník pravého potomka • vlož na zásobník levého potomka Post-order Bere nejdriv levy a obe vetve a az pak rodice – vlož kořen na zásobník – dokud není zásobník prázdný, opakuj • vyber uzel z vrcholu zásobníku • pokud je neoznačkovaný o označkuj jej a ulož jej zpět na zásobník o ulož na zásobník pravého potomka o ulož na zásobník levého potomka • pokud je označkovaný o zpracuj jej In-order Po vertikalnich carach zleva – vlož kořen na zásobník – dokud není zásobník prázdný, opakuj • v := uzel na vrcholu zásobníku • dokud má v nezpracovaného levého potomka, opakuj o vlož levého potomka uzlu v na zásobník o v := uzel na vrcholu zásobníku • opakuj o vyber uzel z vrcholu zásobníku a zpracuj jej • dokud vybraný uzel nemá pravého potomka a zásobník není prázdný • má-li vybraný uzel pravého potomka, vlož tohoto potomka na zásobník
Vlozeni prvku do AVL stromu • Vložíme uzel jako v BVS • Aktualizujeme koeficienty vyváženosti • Provedeme vyvážení pomocí cyklických záměn ukazatelů – levá nebo pravá rotace: novým kořenem se stává kořen vyššího podstromu – maximálně dvě (protisměrné) rotace na jedno vložení Vkládání do prioritního stromu • Vložíme nový uzel na nejbližší volnou pozici tak, aby strom zůstal zleva úplný • Dokud má vkládaný uzel větší prioritu, než jeho rodič, vyměníme je o “probubláváme” s uzlem směrem nahoru na správné místo • Maximální počet výměn je h = log2n Vybírání z prioritního stromu • Vždy vybíráme kořen o protože má nejvyšší prioritu • Na jeho místo vložíme nejpravější list (L) maximální výšky o kvůli zachování levé kompletnosti stromu • Dokud má L nižší prioritu než některý z jeho potomků, vyměníme jej s potomkem vyšší priority o “probubláváme” s uzlem směrem dolů • Maximální počet výměn je h = log2n
KLASICKE GRAFY Obecny algoritmus prohledavani • Vstup: Souvislý graf G • Výstup: Posloupnost všech uzlů grafu G • Inicializace: Libovolný uzel označkuj a vlož do D • Dokud je D neprázdné, opakuj – Vyber uzel, který je na řadě – Zpracuj / vypiš jej – Všechny jeho neoznačkované následovníky • označkuj a vlož do D • D = fronta / zásobník podle způsobu prohledávání • Díky značkování zpracujeme každý uzel právě jednou
Počet koster obecného – artikulacemi rozdělíme graf na části, které • vždy obsahují všechny hrany mezi danými uzly • jsou buď stromy, cykly nebo úplné grafy – určíme počty koster jednotlivých podgrafů – vynásobíme počty koster mezi sebou
MINIMALNI KOSTRY Jarníkův-Primův-Dijkstrův algoritmus – Vyber libovolný uzel – Dokud existují nevybrané uzly – Vyber nejkratší hranu spojující některý vybraný uzel s nevybraným – Přidej vybranou hranu a nevybraný incidentní uzel Kruskalův hladový algoritmus • Množinu hran seřadíme vzestupně podle hranového ohodnocení • Postupně budujeme nový graf – začínáme pouze s uzly (tj. „diskrétní faktor“) – přidáváme hrany dle pořadí délek – pokud by přidáním hrany vznikla kružnice, hranu nepřidáváme • spojujeme tedy jen uzly ležící v různých komponentách – pokusíme se přidat všechny hrany Borůvkův-Sollinův algoritmus • Je dán souvislý graf G = (U, H) – s hranami různé délky • T := • Dokud (U, T) není souvislý graf, opakuj: – E := – Pro všechny komponenty (U, T) • Do E přidej nejkratší hranu spojující uzel dané komonenty s uzlem mimo komponentu – T := T E • (U, T) je minimální kostra grafu G
Hledani mostu • Vstup: Souvislý graf G • Výstup: Seznam mostů v grafu G • Inicializace: Nastav H := G • Opakuj dokud |UH| > 1 – buduj DFS-cestu tak dlouho, dokud nedosáhne dokončeného vrcholu t – jestliže stupeň t je roven 1 • označ hranu incidentní s t jako most • H := H – t – jinak (uzel t a všichni jeho sousedé leží na cyklu C) • Proveď kontrakci cyklu C
Terryho algoritmus (cesta z bludiste) – Založen na značkování dveří podle následujících pravidel: – vstoupíš-li do místnosti, kde žádné dveře nejsou označeny, označkuj vstupní dveře “IN” – jsi-li v místnosti s alespoň jedněmi neoznačkovanými dveřmi, vyber si libovolné, označ je “OUT” a projdi chodbou za nimi do následující místnosti – jsi-li v místnosti, kde jsou všechny dveře označeny, vstup do dveří označených “IN” – vstoupíš-li do místnosti, kde jsou všechny dveře označeny “OUT”, z bludiště není východ
NEJKRATSI CESTA Moorův algoritmus • Prohledávání grafu do šířky • Každý uzel má značku (p,d), kde d je délka cesty (počet hran) a p je předcházející uzel • Počáteční uzel s dostane značku (-,0), ostatní (-,nekonecno). V0 = {s}, k=0 • Pro kazde i z Vk uděláme – každého neoznačkovaného následníka uzlu i označkujeme (i, k+1) a vložíme jej do množiny Vk+1 • Zvýšíme k o 1 a pokud Vk není prazdna mnozina, opakujeme • Výsledkem je distanční rozklad množiny uzlů Dijkstrův algoritmus • Každý uzel má značku (p,d), kde d je délka cesty (součet délek hran) a p je předcházející uzel • Značky jsou trvalé (množina S) a netrvalé (množ. Š) • Počáteční uzel s dostane trvalou značku (-,0), jeho následníci (s, d), ostatní (-,nekonecno). S = {s}, Š=U-S • Dokud Š není prazdna mnozina – V množině Š vybereme uzel k s nejmenší vzdáleností od množiny S – Přesuneme jej do S – Prověříme značky všech následníků uzlu k z množiny Š a v případě potřeby je aktualizujeme
Bellman-Fordův algoritmus • Každý uzel dostává značku (a, p, d), kde a je počet hran nejkratší cesty, d její délka a p předposlední uzel • Počátek s dostane značku (0, -, 0), ostatní uzly (0, • Dokud je k<|U| – Pro každý uzel j, kde a=k • Prověříme značky všech následníků i uzlu j a v případě potřeby je aktualizujeme • di = dj + dij • pj = i • aj = ai+1 • Zvýšíme k o 1 Floyd-Warshallův algoritmus • Graf zadaný maticí sousednosti (D(0)) obsahující délky hran nebo nekonecno; na diagonále nuly • Výstupem je matice, z níž lze zjistit nejkratší cesty mezi všemi uzly • Konstruujeme posloupnost matic D(1), D(2), … D(n) tak, že
• Každý prvek matice obsahuje délku nejkratší cesty z i do j, obsahující vnitřní uzly 1..k • Pro všechna k = 1..|U| konstruujeme k-tou matici z k-1-ní po řádcích, k-tý řádek se nemění • Cestu z i do j pak rekonstruujeme rekurzivně, hledajíce postupně taková l, kde dij=dil+dlj • Záporné číslo na diagonále znamená existenci záporného cyklu Algoritmus hledání uzavřeného eulerovského tahu • Vstup: Souvislý graf G s uzly jen sudého stupně • Inicializace – vyber libovolný uzel a najdi kružnici T, která jím prochází • Iterace: dokud existují hrany nepoužité v tahu T – najdi libovolný uzel u ležící v T obsahující nepoužité hrany – vytvoř kružnici D z nepoužitých hran obsahující uzel u • lze využít modifikovaný algoritmus prohledávání do hloubky – přidej k T “odbočku” D
OBCHODNI CESTUJICI Hladová strategie nejbližšího souseda –z každého města se vydáme tam, kam to máme nejblíže –velmi rychlý algoritmus –mnohdy poskytující velmi špatná řešení Algoritmus zdvojení stromu • Vstup: úplný graf G s hranovým ohodnocením splňujícím trojúhelníkovou nerovnost • Výstup: HC maximálně 2x delší,než nejkratší • Příprava – Najdi minimální kostru T grafu G – Zdvoj každou hranu a sestroj eulerovský tah E kostrou T • Konstrukce HC H – začni v libovolném uzlu – sleduj tah E a přidávej navštívené uzly do H, dokud následující hrana nevede do již navštíveného uzlu – najdi nejbližší nenavštívený uzel na E a přidej jej do H • tím vyrobíme “zkratku” obcházející již navštívené uzly – opakuj poslední dva kroky, dokud nedosáhneš počátečního uzlu Algoritmus párování ve stromu •Vstup: úplný graf G s hranovým ohodnocením splňujícím trojúhelníkovou nerovnost •Výstup: HC maximálně 1,5x delší,než nejkratší •Najdi minimální kostru T grafu G •Nechť O je množina uzlů lichého stupně v kostře T •Najdi minimální perfektní párování M v O •Najdi eulerovský tah v grafu E •Najdi hamiltonovskou kružnici stejně jako v algoritmu zdvojení stromu (pomocí zkratek)
MAXIMALNI TOK V SITI Fordův-Fulkersonův algoritmus • U každé hrany udržujeme dvojici (tok, kapacita) • Nalezneme rezervní polocestu ze zdroje do stoku • Identifikujeme nejmenší rezervu d hrany na této cestě – to je rezerva polocesty • Na hranách ve směru cesty zvýšíme tok o d • Na hranách proti směru cesty snížíme tok o d • Opakujeme tak dlouho, dokud existuje rezervní cesta Edmonds-Karpův algoritmus •Inicializace – nastav tok ve všech hranách na nulu •Iterace – Najdi nejkratší rezervní cestu Moorovým algoritmem – Každý uzel dostane značku (p,+-,d, s) • p = předchůdce • + = hrana je ve směru cesty (následník) • = hrana je proti směru cesty (předchůdce) • d = vzdálenost od zdroje • s = rezerva cesty – Při zpracování uzlu i dostane každý neoznačkovaný • následník j značku (i,+,di+1,min(s,cij-fij)) • předchůdce j značku (i,-,di+1,min(s,fij)) • Zvyš/sniž tok všech hran rezervní cesty o její rezervu • Opakuj, dokud existuje rezervní cesta Dinicův algoritmus • Začneme s libovolným tokem f (např. prázdným) •
Dokud to jde, zlepšujeme tok opakováním: – Vytvoříme rezervní síť • uzly jsou tytéž, kapacity hran jsou dány rezervami – Najdeme nejkratší s-t cestu • pomocí prohledávání do šířky => distanční rozklad uzlů => vrstvy – Pročistíme síť • odstraníme hrany spojující uzly ve stejné vrstvě • odstraníme hrany vedoucí zpět – Najdeme blokující tok fB v pročištěné síti • alespoň jedna hrana se nasytí – zlepšíme původní tok f podle fB
Goldbergův algoritmus I. • U každého uzlu udržujeme jeho výšku • Ke každé hraně přidáme protisměrnou hranu s nulovou kapacitou – Vždy platí, že f(u,v) = -f(v,u) • Vlna splňuje kapacitní omezení hran, nemusí splňovat zákon zachování toku – v uzlech jsou povoleny přebytky – uzel s přebytkem je aktivní • Dvě operace – zvednutí uzlu = zvýšení výšky tak, aby byl o 1 výš než nejnižší z následníků na rezervních hranách – protlačení vlny = zvýšení toku hrany o minimum z rezervní kapacity a přebytku počátku postup: • Nastav v(s) = |U|, výšku ostatních uzlů na 0 •
•
Nasyť všechny hrany vedoucí ze zdroje – koncové uzly se stávají aktivními – přidej je do fronty Dokud není fronta aktivních uzlů prázdná – odeber uzel z fronty –
existuje-li nižší následník na rezervní hraně, protlač vlnu po této hraně
–
jinak zvedni uzel
–
je-li uzel stále aktivní, přidej jej na konec fronty
HLEDANI PAROVANI Algoritmus hledání maximálního párování pomocí střídavých cest – – najdeme zlepšující cestu C začínající ve volném vrcholu z A a končící ve volném vrcholu z B – – opakujeme dokud existuje zlepšující cesta Algoritmus hledání zlepšující cesty • • • •
Iterace: Dokud jsou v S neoznačené uzly, opakuj – neobsažené v párování je-li y nepokrytý, našli jsme zlepšující cestu – tuto cestu zrekonstruujeme pomocí značek u každého uzlu
• •
přidej y do T, zaznamenej k němu „x“ – označ uzel x Nejsou-li v S
– S) minimální uzlové pokrytí
Největší párování pomocí toku • Předpokládejme bipartitní graf G = ((A,B),H) – orientace hran je vždy z uzlu ležícího v A do uzlu ležícího v B • Graf G rozšíříme na síť přidáním nových uzlů s a t •
pro každé u z A přidáme hranu (s,u) o kapacitě 1
•
pro každé v z B přidáme hranu (v,t) o kapacitě 1
• •
pro každou hranu h z H nastavíme c(h)=L – kde L je libovolné velké číslo najdeme maximální tok z s do t
•
tok jednoznačně určuje maximální párování
BARVENI GRAFU Sekvenční barvení grafu • Položme K=0 – počet dosud použitých barev • Dokud existuje neobarvený uzel •
Vybereme neobarvený uzel
•
Určíme nejnižší přirozené číslo b, které může být obarvením uzlu a obarvíme jej
• Je-li b>K, aktualizujeme K pravidla pro výběr uzlu • Náhodně •
•
•
Nerostoucí posloupnost podle velikosti stupňů – nejdříve barvíme uzly s nejvyšším stupněm – nakonec barvíme uzly s nejnižším stupněm Pro každý uzel určíme počet barev, které již byly použity k obarvení jeho sousedů – vybereme uzel s nejvyšší hodnotou – v případě rovnosti volíme ten, který má více neobarvených sousedů Smyslem je „zbavit se“ nejprve nejobtížnějších uzlů
Barvení grafu pomocí nezávislých množin • Množina uzlů A se nazývá nezávislá právě tehdy, když neexistuje hrana, která by spojovala dva uzly ležící v množině A •
Pro dané obarvení grafu je každá barevná třída nezávislá
•
Algoritmus barvení grafu – zvolíme neobarvený uzel u (podobně jako u sekvenčního barvení) –
určíme největší nezávislou množinu N(u) uzlů obsahující u
–
obarvíme uzly z množiny N(u) novou barvou
–
opakujeme tak dlouho, dokud existují neobarvené uzly
Barvení grafu slepováním uzlů • Dokud graf není úplný – vyber dva nesousední uzly u a v –
•
vybrané uzly nahraď jedním, který bude sousedit se všemi, s nimiž sousedily uzly u a v Obarvi každý uzel úplného grafu jinou barvou
•
Uzly znovu rozděl
Nedokonalé barvení v hranově ohodnoceném grafu • Problém: Sestavování rozvrhu hodin – uzly = předměty – hrany = požadavky na umístění v různou hodinu – ohodnocení hran = vážnost požadavku • stejný vyučující • počet studentů registrujících stejný předmět – obarvení = umístění do časových slotů • H(G) • Kolize = hrana spojující uzly obarvené stejnou barvou • •
Hledáme obarvení grafu s nejmenším součtem kolizí Algoritmy založené na sekvenčním barvení grafu – nejprve se zbavujeme uzlů spojených hranami s nejvyšší váhou
