Obsah:

Cvičení se zabývá základními grafovými algoritmy, tedy průchody do šířky a 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 a hledáním koster.

Implementační zadání:

• Zadání v C:

• Zadání v Pythonu:

Doplňkové materiály: