IB002 Algoritmy a datové struktury I
11. cvičení: Průzkum grafů - DFS
Obsah:
Cvičení se zabývá základními grafovými algoritmy, tedy průchody do hloubky. Průchody se následně aplikují na určování silně souvislých komponent grafu, hledání cyklů a určování typu hran podle průchodu DFS. Grafy jsou reprezentovány buďto maticí vzdáleností, nebo seznamem následníků, studenti se naučí převádět mezi těmito reprezentacemi.
Po tomto cvičení byste měli být schopni identifikovat případy, v nichž se dá zvolit k reprezentaci dat graf. Na grafech byste měli znát průchody do šířky a do hloubky, jejich vlastnosti a užití. Měli byste mít všechny potřebné znalosti pro navazující cvičení, které se zabývá hledáním nejkratší cesty v grafu.
Implementační zadání:
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/jaro2023/IB002/um/ducv/du11_graph_components.py