17.04.2024 st 
Programovani 2 pro Matematiky

Teoretické cvičení
1. Opakovani DFS a BFS

1.1 Mějme (neorientovany) graf G DFS a BFS z vrcholu
Vypiste poradi vrcholu daneho grafu G:
a] DFS: 
	a1] preorder
	a2] postorder
b] BFS:
z vrcholu x, poradi potomku vrcholu je dano sestupne tzn. od vrcholu s nejvetsi hodnotou k nejmensi hodnote


1.5 Nejkrasi cesta v grafu z vrcholu x do vrcholu y
(cim se meri? pocet hran)

2.2 Dijkstra 
hranove ohodnoceny graf
varianty A to B vs A to vše
podminky na graf
simulace behu
kdy se agoritmus zastavi? co je zastavovaci podminka? 
je algoritmus konecny? 
co vlastne vraci Dijkstra?
slozitost?

Dijkstra vs A*
- informovane prohledavani
- vizualizace ("kruznice vs oval") a protipriklady (U prekazky), priklad realna vizualizace na mape: https://medium.com/@miguell.m/dijkstras-and-a-search-algorithm-2e67029d7749 

FloydWarshal algo

4. Minimalni kostra 

5. Topologicke usporadani
2 varianty
- motivace, pouziti
- priklady



Praktické cvičení

1. Implementujte algoritmus vracející topologické uspořádání orientovaného grafu (vracející: list vrcholů v topologickém uspořádání), pokud graf není topologicky uspořádatelný vrátí list obsahující "-1" tj. [-1]. 
Graf je zadán seznamem sousedů (list listů).
- aditive vertex, why?

1.3 Upravte algoritmus topologickeho usporadani pro detekci acyklicnosti grafu.
is_acyclic(G), v pripade ze grag G neobsahuje kruznici vraci True, jinak False 

1.5 Upravte algoritmus topologickeho usporadani pro detekci acyklicnosti grafu a tim, ze nalezenou kruznici vypise.