zpět
Cvičení 9 - Topologické třízení vrcholů orientovaného grafu.
Zadání cvičení:
- Prostudujte si ukázkovou minimální implementaci orientovaného grafu.
- Jedná se o modifikovanou a osekanou verzi neorientovaného grafu z osmého cvičení.
- Vrchol obsahuje navíc proměnnou indegree reprezentující počet příchozích hran a booleovskou proměnnou visited, které budou využity během topologického třízení .
- Implementujte topologické třízení realizované algoritmem Source Removal využívající frontu podle následujícího pseudokódu.
- Jakou vlastnost musí graf splňovat, aby bylo existovalo topologické uspořádání uzlů?
- Implemetovat budete dvě funkce - funkci Init, která incializuje hodnotu proměnné visited na false a indegree na příslušnou hodnotu u každého vrcholu (řádky 2 a 3 v pseudokódu), a funkci SourceRemoval realizující zbytek algoritmu.
- Otestujte algoritmus na přiložených testovacích grafech, vyzkoušejte jaký bude výsledek algoritmu v případě že topologické uspořádání neexistuje.
Šablona:
Graph.h
Graph.cpp
cviceni9.cpp
Ukázkové vstupní soubory:
graph1.txt
graph2.txt
graph3.txt
graph4.txt
Řešení:
Graph.cpp
