Grafové algoritmy Programovací techniky
Grafy – Úvod - Terminologie • Graf je datová struktura, skládá se z množiny vrcholů “V” a množiny hran mezi vrcholy “E” • Počet vrcholů a hran musí být konečný a nesmí být nulový u vrcholů ani u hran • Grafy – Orientované – hrana (u,v) označena šipkou u->v – Neorientované – pokud ex. (u,v), existuje také (v,u) • Souvislost – graf je souvislý, jestliže pro všechny v(i) z V existuje cesta do libovolného v(j) z V, nesouvislý graf je rozdělen na komponenty • Strom – graf, ve kterém pro každé 2 vrcholy existuje právě jedna cesta
Grafy – Úvod - Terminologie
Grafy – Úvod – Reprezentace grafu Incidenční matice:
Matice sousednosti:
Spojové seznamy: - výhodné pokud je proměnný počet hran
Neorientovaný graf:
Plexová struktura: - princip podobný reprezentaci seznamem, ale statické pole je nahrazeno dynamickým spojovým seznamem - výhodné pokud používáme proměnný počet uzlů Orientovaný graf: 1
2
4
2
3
/
3
4
/
4
2
5
1
5
/
5
/
/
Neorientovaný graf:
1
2
4
5
2
1
3
4
3
2
4
4
1
2
5
1
4
/
/ 3
5
/
/
Ohodnocené grafy • hrany grafu jsou ohodnoceny (např. délka cesty mezi dvěma městy, doba potřebná k projetí apod.) • reprezentace grafů incidenční maticí je obdobná, akorát místo hodnot ±1 je uvedeno ohodnocení hrany, 0 se obvykle nahrazuje symbolem ∞. • pokud reprezentujeme graf spojovým seznamem nebo plexovou strukturou má položka seznamu tvar u
h
Ukazatel na další prvek
ohodnocení hrany Uzel ve kterém hrana končí
Prohledávání grafu • Systematický postup pro řešení následujících úloh: Zjistit, zda vrchol t je dosažitelný z vrcholu r Najít množinu všech vrcholů dosažitelných z vrcholu r Najít jakoukoliv cestu z vrcholu r do vrcholu t (pokud existuje) Najít jakékoliv cesty z vrcholu r do všech vrcholů, které jsou z něj dosažitelné 5. Pro všechny vrcholy, které jsou dosažitelné z vrcholu r provést zadanou operaci 1. 2. 3. 4.
Metody prohledávání: • prohledávání do hloubky (depth-first search) • prohledávání do šířky (breath-first search) • heuristické prohledávání
Prohledávání grafu do hloubky
Časová složitost prohledávání do hloubky: O(|V|+|H|)
Prohledávání grafu do šířky
Časová složitost prohledávání do šířky: O(|V|+|H|)
Vyhledávání nejkratší cesty v grafech Úkolem této skupiny algoritmů je nalézt nejkratší orientovanou cestu: • z daného vrcholu do daného vrcholu, • z daného výchozího vrcholu do každého vrcholu grafu, • z každého vrcholu do daného koncového vrcholu, • mezi všemi uspořádanými dvojicemi vrcholů Algoritmy jsou založeny na prohledávání grafu, do kterého je přidáno kritérium při výběru hran - délka cesty (součet cen všech hran, které tvoří cestu z výchozího vrcholu do koncového vrcholu). Pokud nalezneme jakoukoliv cestu z výchozího vrcholu do libovolného dalšího, testujeme, je-li to nejkratší cesta – ověřujeme platnost trojúhelníkové nerovnosti
cj >ci+cij, Kde cj je cena dosud nejkratší cesty z výchozího vrcholu do vrcholu vj, cij je cena hran mezi vrcholy vi a vj. Pokud je nerovnost splněna, nalezli jsme lepší cestu a cj :=ci+cij, pokud ne neměníme nic.
Základní algoritmus
Zlepšený algoritmus
Dijkstrův algoritmus • Hledání nejkratší cesty v ohodnoceném grafu z vrcholu s do vrcholu t • Předpokládáme: – Graf je souvislý – Neorientované hrany (lze použít i pro orientované grafy) – Má nezáporně ohodnocené hrany
• Z navštívených vrcholů vytváříme mrak. Zpočátku mrak obsahuje počáteční vrchol S, postupně přidáváme uzly až do nalezení cílového uzlu • V každém kroku – přidáme do mraku vrchol v vně mraku s nejmenší vzdáleností d(v) (prioritní fronta) • Opravíme vzdálenosti vrcholů sousedících s v (vede často k relaxaci hran)
Dijkstrův algoritmus • Relaxace hran – Relaxace hrany e upravuje vzdálenost d(z) takto: d(z) min{d(z),d(u)+weight(e)}
Bellman-Fordův algoritmus • podobný Dijkstrovu algoritmu, • v algoritmu je zavedeno další pole, ve kterém je u každého vrcholu uvedeno, kolik hran obsahuje nejkratší cesta z výchozího vrcholu do daného vrcholu. • algoritmus preferuje nejkratší cestu s nejmenším počtem hran • algoritmu lze využít k detekci cyklu se zápornou cenou – v grafu o n vrcholech je maximálně n-1 hran ⇒ pokud algoritmus neskončí po n-1 krocích je v grafu cyklus se zápornou cenou.
Bellman-Fordův algoritmus
Floyd-Warshallův algoritmus • Algoritmus hledající minimální cestu mezi všemi páry vrcholů (all-pair shortest path algorithm) • Vhodný pro husté grafy – v tom případě rychlejší než Dijkstra opakovaný pro všechny vrcholy • Pracuje s maticí sousednosti • Složitost O(n3) • Můžeme stanovit max. počet vrcholů, přes které se jde • Je technikou dynamického programování – viz dále
• • • •
Matice sousednosti je uložena ve w d je matice aktuálně spočtených nejkratších vzdáleností mezi je matice nejkratších mezicest, je nainicializována na -1 (null) V každém kroku algoritmu zjišťuji, jestli existuje mezi vrcholy i,j kratší cesta přes vrchol k, pokud ano, nastavím vzdálenost v d[i][j] na novou velikost a do path[i][j] zaznamenám vrchol k
Floyd-Warshallův algoritmus
Floyd-Warshallův algoritmus • Rekonstrukce nejkratší cesty mezi i,j – V mezi[i,j] je index vrcholu k, přes který se má jít. Pokud k není 1(null) podívám se do mezi na nejkratší cestu mezi i,k a k,j – Toto opakuji rekurzivně dokud nenajdu mezi[i,j] == -1 null). Cesta(i,j) begin if mezi[i,j]=null then tisk(i,j) else begin Cesta(i, mezi[i,j]); Cesta(mezi[i,j], j); end; end;
Minimální kostra grafu • Algorimus na hledání minimální kostry grafu (Minimum Spanning Tree) Kostra grafu: – minimální souvislý podgraf, který obsahuje všechny vrcholy – neobsahuje cykly – je to strom Definice: Je dán souvislý graf G, jehož hrany jsou ohodnoceny reálnými čísly, které budeme nazývat cenami. Kostrou grafu, která má nejmenší ohodnocení hran mezi všemi kostrami, nazýváme „nejlevnější (minimální) kostrou grafu“
Kruskalův algoritmus:
Primův – Jarníkův algoritmus
Prim- Jarnikův algoritmus (využívá prioritní frontu) for ∀u∈V do begin klíč[u]:=∝ uvnitř[u]:=False end; klíč[r]:=0; před[r]:=nil; Q:=prioritní_fronta(V); {vložení vrcholů do prioritní fronty Q} while Neprázdná(Q) do begin u:=OdeberMin(Q); for ∀v∈Adj[u] do if (not(uvnitř[v])) and (w[u,v]
Primův-Jarníkův algoritmus • Příklad(1)
Primův-Jarníkův algoritmus • Příklad - pokračování
Toky v sítích
Příklady grafů se zadanou velikostí toku, kapacitou hrany a dolním omezením.
Maximální tok sítí
Příklad:
