====== Cvičení 10: Grafy ======
===== Quick test 1 - data =====
{{ :courses:b3b33alp:cviceni:slovnik.txt | slovnik.txt}}
==== Reprezentace grafu ====
* Graf lze reprezentovat maticí sousednosti, seznamem hran nebo seznamem odchozích hran
* Budeme používat seznam odchozích hran.
{{courses:b3b33alp:cviceni:graph5forbfs0000.png?200|}}
* Pro graf na obrázku bude reprezentace vypadat takto:
* G je proměnná typu dictionary, indexujeme ji jménem (číslem) uzlu, hodnota je pole, které obsahuje seznam uzlů, které jsou dosažitelné
G = {}
G [0] = [1 ,2 ,5]
G [1] = [0 ,2]
G [2] = [0 ,1 ,3]
G [3] = [2]
==== Načtení grafu ze souboru ====
Mějme orientovaný graf, který má uzly očíslované od 1 do N. Hrany v tomto grafu jsou zadány v souboru, který na jedné řádce obsahuje definici jedné hrany, tedy dvě čísla:
* první číslo je číslo uzlu ze kterého vede hrana
* druhé číslo je číslo uzlu do kterého vede tato hrana
Napište program ''path.py'', který z příkazové řádky načte jméno souboru s definicí hran a číslo startovního uzlu a číslo koncového uzlu. Program vytiskne jednu z nejkratších cest ze startovního uzlu do cílového uzlu.
Program otestujte na tomto souboru:
1 2
1 9
2 3
2 6
3 4
3 8
4 6
4 1
5 4
5 8
6 8
6 9
7 4
7 5
8 7
8 3
9 5
9 1
Výsledek pro cestu z uzlu 2 do uzlu 5 je:
2 6 9 5