Search
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.
graph
graph.hpp
Do grafu lze přidat uzly dvěma způsoby:
init_graph(g, n)
g
n
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.
init_graph
add_vertex
num_vertices(g)
num_vertices(g)-1
Další funkce k implementaci:
add_edge(g, from, to)
from
to
connections(g, from)
reachable_vertices(g, from)
clear_graph(g)
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ěť.
.cpp
Při hledání dosažitelných uzlů se vám pravděpodobně bude hodit fronta (hlavička <queue>).