Cvičení 7 - Algoritmy průchodu grafem

• Prostudujte si ukázkovou implementaci neorientovaného grafu využívající seznam sousedních vrcholů.
• Vrchol grafu je reprezentovan strukturou Node. Opět uvažujeme označení vrcholů čísly 0 až n-1, kde n je počet vrcholů grafu.
• Každý vrchol obsahuje seznam (tj. vektor) souseních vrcholů.
• Graf je definován jako seznam (tj. vektor) vrcholů.
• Graf je načítán ze souboru ve stejném formátu jako na minulém cvičení.
• V grafu je implementován rekurzivní a nerekurzivní průchod do hloubky a nerekurzivní průchod do šířky. Prostudujte tyto algoritmy a vyzkoušejte je na testovacích grafech.
• Implementované průchody prochází pouze jednu souvislou komponentu grafu.
• Iterativní průchody používají standardní implementace zásobníku a fronty z STL library.
• Průchody projdou a zpracuji (tj. vytisknou) jednotlivé vrcholy.
• Ukázkový průchod do šířky navíc vypíše a uloží do každého vrcholu informaci o jeho (nejkratší) vzdálenosti od počátečního vrcholu.
• Vyuzijte průchod do šířky a implementujte funkci GetNodesWithGivenDistance která vrátí vektor vrcholů (jejich číselných hodnot), které jsou v určité vzdálenosti od počátečního vrcholu.
• Stávající průchod do šířky můžete skopírovat a upravit.
• Pokud ve funkci projdete všechny vrcholy s požadovanou vzdáleností, průchod zastavte.
• Využijte průchod do hloubky (vyberte si zdali rekurznivní nebo iterativní) a implementujte funkci ComponentSums pro průchod všech komponent, která pro daný graf vráti vektor čísel (pro každou komponentu jedno) reprezentující součet čísel vrcholů v komponentě.
• Stávající průchod do hloubky můžete skopírovat a upravit.