Harjutustund nr 5

Graafialgoritmid: harjutusülesanded
-----------------------------------
1. Laiutiotsing (breadth-first search)
Alustasime eelmisel harjtustunnis. Kuidas õnnestus kodus lõpetamine? Lahenuse üks võimalik variant on lahenduste kaustas näha.

2. Dijkstra algoritm.
Milline on Dijkstra algoritmi erinevus laiutiotsingust? Nüüd tuleb arvestada kaarte kaaludega ning uus tee, mis küll kaarte
arvult suurem, võib kaale arvestades hoopis lühem (kergem?) olla. Seega tuleb Dijkstra algoritmis võrrelda vana ja uut teepikkust ning 
vajadusel teid muuta.
Uurime algoritmi näite abil (lingid kursuse veebis 4.4 kuupäeva all)
Edasi proovi ise, kasutades laiutiotingust juba tuttavat faili BFS_ja_Dijkstra_harjutus.pdf (.odg). Alusta taas tipust A ja leia lõpuks lühim tee
tippu G.

3. Süvitiotsing (depth-first search)
Näitefail: DFS.odg
Tekib süvitiotsingu puu, samuti fikseeruvad sammud, millal tippu esimesena töödelda saab ja millal tipust lõplikult
lahkutakse (st millal on kõik sellest tipust edasi olevad tipud läbi käidud). 
Süvitiotsingu puu sisaldab kõikki graafi tippe ja vaid neid kaari, mida on vaja kõigi tippudeni jõudmiseks.

Tüüpiline analoogia on labürindi läbimine.
Failid: labyrindi_graaf.odg, labyrint_ja_graaf.pdf

4. (Minimaalse) toesepuu leidmine ((minimum) spanning tree)
Toesepuud leitakse orienteerimata graafis. Kaalutud graafis võib rääkida minimaalsest 
toesepuust - so toesepuu, mille kaarte kaalude summa on minimaalne.

Min_toesepuu_leidmine.odg

Kruskal'i ja Prim'i algoritmid on minimaalse toesepuu leidmiseks.
http://en.wikipedia.org/wiki/Kruskal%27s_algorithm
http://en.wikipedia.org/wiki/Prim%27s_algorithm

Kruskal'i algoritmi kohaselt valitakse minimaalse kaaluga serv ja ta sobib toesepuusse siis, kui ta ühendab kaks seni 
ühendamata graafi osa.
Tegemist on nn ahne algoritmimisstrateegiaga (Greedy algorithm). Selle strateegia kohaselt toimub tegevus sammudena 
ja igal sammul tehakse hetkel parimana näiv otsus. Kruskali algoritmi kontekstis - valitakse vähima kaaluga serv, sest
sellise puusse lisamisel peaks tekkima ka minimaalne toes.

Prim'i algoritmi järgi valitakse toesepuusse samuti neid servi, mis on minimaalse kaaluga, kuid lisatingimusel, et 
ta peab ühendama seni tekkinud puuga uue tipu (mitte lihtsalt kaks suvalist tippu).

KODUS: lõpuni läbi mõelda ja ära teha Dijkstra algoritmi tabelid.