09.04.2025 st 
Programovani 2 pro Matematiky

Teoretické cvičení

0. Reprezentace grafu
- opakovani typu reprezentaci grafu
- napiste funkci prevadejici reprezentaci grafu seznamem sousedu (2D list) na matici sousednosti
- napiste funkci prevadejici reprezentaci grafu seznamem sousedu (2D list) na matici incidence
- navrhnete funkci rozhodujici, zdali je graf orientovany
- jaky je a co urcuje soucet radku v matici incidence 
- jaky je a co urcuje soucet sloupce v matici incidence 
- jaky je a co urcuje soucet radku v matici sousednosti
- jaky je a co urcuje soucet sloupce v matici sousednosti 
- jak se zmeni reprezentace grafu, pokud budeme chtit reprezentovat hranove ohodnoceny graf
- jak se zmeni reprezentace grafu, pokud budeme chtit reprezentovat orientovany graf
- ktere reprezentace se hodi pro ridke (sparse) grafy a ktere pro "huste"



1. DFS a BFS
T - BT - T - connected Graph - oriented Graph - unconnected Graph - State Space 

# meli jsme pruchod stromem, tedy souvislym grafem bez kruznic
# presneji prochazeli jsme binarni strom
# take jsem si vyzkouseli ruzne druhy pruchodu:
# a] do hloubky (rekurzi i zasobnikem)
# b] do sirky frontou

# pro pruchod do hloubky jsme meli pre-, in- a post- order poradi
#
# nyni rozsirime prochazeni stromu na obecny graf:
# a] souvisly graf - resime cykly resp. navstivene vrcholy
# b] nesouvisly graf - navic resime kompomenty grafu

# a nasleduje pruchod stavovym prostorem (soused stavu neni "pevne zadratovan jako v pripade grafu")
# ale je generovan dle pravidel


# 1.3 Graf
# graf reprezentovan seznamem sousedu
g = [
    [1, 4],  # 0
    [0, 2, 5],  # 1
    [1, 3, 6],  # 2
    [2, 4, 8],  # 3
    [0, 3, 7],  # 4
    [1, 6, 7],  # 5
    [2, 5],  # 6
    [4, 5, 8, 9],  # 7
    [3, 7, 9],  # 8
    [7, 8],  # 9
]

# unconnected graph
h = [
    [1, 4],  # 0
    [0, 2, 5],  # 1
    [1, 3, 6],  # 2
    [2, 4, 8],  # 3
    [0, 3, 7],  # 4
    [1, 6, 7],  # 5
    [2, 5],  # 6
    [4, 5, 8, 9],  # 7
    [3, 7, 9],  # 8
    [7, 8],  # 9
    [11, 12],  # 10
    [10, 12],  # 11
    [10, 11],  # 12
    [],  # 13
]



1.3.2 Nakreslete graf g
1.3.5 Na papire graf projdete pre a post order DFS z vrcholu: 
(v jakem poradi prochazime sousedy vrcholu)
 a] z vrcholu 0
 b] z vrcholu 7
1.3.6 Jak byste v grafu detekovali kruznici?
(zpetna hrana vs kruznice)


# 2. Implementujte rekurzivni DFS na souvislem grafu

# 2.5 Implementujte DFS pomoci stacku na souvislem grafu

# 3. jak se zmeni implementace dfs na obecnem i nesouvislem grafu?
# pruchod grafem vs pruchod grafem z vrcholu

# 3.5 naimplementujte funkci, ktera vypise pocet kompoment grafu


b] BFS:
z vrcholu x, poradi potomku vrcholu je dano sestupne tzn. od vrcholu s nejvetsi hodnotou k nejmensi hodnote
z vrcholu 0

Implementujte BFS pro souvislý graf 

4. Nejkrasi cesta v grafu z vrcholu x do vrcholu y
(cim se meri?  ted pocet hran)
z vrcholu 0 do vrcholu 7

5.1 Naimplementujte hledani nejkratsi cesty v grafu z vrcholu v do vrcholu w merene poctem hran 
5.1.2 funkce vrati delku nekratsi cesty 
5.1.3 funkce vrati nekratsi cestu listem vrcholu  


5.3 Naimplementujte funkci isBipartity(g), ktera vraci True, pokud je graf bipartitni a False, pokud neni bipartitni


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 
(vizualizace Dijkstra vs A*; je uveden i pocet navstivnych vrcholu)

FloydWarshal algo

4. Minimalni kostra 

5. Topologicke usporadani
2 varianty (trhani listi, reverse postorder DFS)
- motivace, pouziti
- priklady




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.

2. Pro zadaný souvisly graf vratte list listu obsahujici vsechny jeho (neduplicitni) kruznice