Grafy a grafové algoritmy

Témata

• grafy a jejich reprezentace
• grafové algoritmy:
  • průchody grafem a jejich varianty
  • Dijkstrův algoritmus

Organizační

• Příští týden budeme psát písemku.
• Podobný styl jako minule:
  • 14 bodů
  • hodina času
  • témata od AVL po grafy
• Více informací zde

Průběh cvičení

Přidám po hodině

Úkoly

1. Implementujte reprezentaci orientovaných grafů pomocí seznamů sousedů.
2. Implementujte průchod grafem do šířky.
3. Implementujte průchod grafem do hloubky.
4. Implementujte Dijsktrův algoritmus.
5. Implementujte reprezentaci grafů pomocí matice sousednosti.
6. Implementujte výše uvedené algoritmy i pro tuto reprezentaci.
7. Složitější: Zkuste navrhnout API pro práci s grafy tak, abyste za ní mohli schovat obě své implementace grafů (seznamem sousedů i maticí sousednosti). Tj. uživatel si bude moci vybrat, která z reprezentací grafu se má použít při jeho vytváření a další volání už budou stejná. Nad toutu API udělejte implemetnaci všech tří algoritmů výše (využíte již napsaných procedur).