09.04.2025 st 
Programovani 2 pro Matematiky

Teoretické cvičení

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

# 0. 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

# a 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
]

1.3.2 Nakreslete graf 
1.3.5 Graf projdete pred a post order DFS z vrcholu xxx a xxx
1.3.6 Jak byste v grafu detekovali kruznici?



# 2. Implementujde dfs na souvislem grafu
visited = [False] * len(g)


# dfs pro souvisly graf
def travers_dfs(v, g):
    visited[v] = True

    # zpracuj_vrchol(v) # provede požadovanou akci
    print("v: ", v, "u: ", g[v])

    # pro všechny hrany (v, u):
    for u in g[v]:
        # print("u:", u)
        if not visited[u]:
            travers_dfs(u, g)


# travers_dfs(7, g)
travers_dfs(6, g)


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




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

Dalsi grafy: 




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.