Ve 2. úkolu budete muset vytvořit strukturu graph, která reprezentuje orientovaný graf. Graf se skládá z uzlů, které jsou navzájem propojeny hranami.

• Implementujte všechny funkce deklarované v souboru graph.hpp.

Do grafu lze přidat uzly dvěma způsoby:

• Pomocí init_graph(g, n), kde g je graf a n je počet uzlů
• Pomocí add_vertex(g)

Při implementaci funkce init_graph můžete uvažovat, že bude pro daný graf volána jenom jednou. Nicméně po volání funkce init_graph může následovat libovolný počet volání add_vertex. Počet vrcholů v grafu lze získat pomocí funkce num_vertices(g). Vrcholy jsou identifikovány čísly 0, 1, 2, …, num_vertices(g)-1.

Další funkce k implementaci:

• add_edge(g, from, to) přidá orientovanou hranu z vrcholu číslo from do vrcholu číslo to
• connections(g, from) vrátí seznam vrcholů, do kterých vede hrana z vrcholu from
• reachable_vertices(g, from) vrátí seznam vrcholů, které jsou dosažitelné z vrcholu from
• clear_graph(g) smaže všechny vrcholy a hrany v grafu

Stáhněte si potřebné hlavičkové soubory a testy.

Jeden nebo více souborů .cpp, které implementují funkce deklarované v souboru graph.hpp tak, aby testy procházely a neztrácela se paměť.

Při hledání dosažitelných uzlů se vám pravděpodobně bude hodit fronta (hlavička <queue>).