Harjutus 
9. aprill 2013

Graafialgoritmid ja ülesanded
-----------------------------
1. Sügavuti otsimine
DSF.odg
Tekib sügavuti otsimise puu, samuti fikseeruvad sammud, millal tippu esimesena töödeldakse ja millal lõpetatakse.

2. Toesepuu leidmine
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 algoritmiga (Greedy algorithm). Selle algoritmimise strateegia kohaselt toimub tegevus sammudena 
ja igal sammul tehakse hetkel parimana näiv otsus. Kruskali algoritmi kontekstis - valitakse vähima kaaluga serv, sest
selliste 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).

3. Proovi sügavuti otsmist ja minimaalse toesepuu leidmist: 
DFS_ja_min_toesepuu_harjutus.odg

4. Dijkstra algoritmi harjutamine (vt eelmise nädala harjutust). 
Oma tabelite kujunemise kontrolliks vaata dijkstra_lahendus.ods lahenduste kaustas.