Jautājums - kāpēc tu to gribi C++ valodā? Vai tai ir kādas priekšrocības tavai problēmai?
Man jau šķiet, ka šai gadījumā būtu izdevīgāka kāda dinamiska valoda. Piemēram, Python. Tur tu grafus varētu ātri un vielgi būvēt no parastiem dict vai list objektiem (std::map un std::vector veida konteineri).

Bet ja nu gribi C++'ā ar boostu, tad RTFM: Boost C++ Libraries - Table of Contents: Boost Graph Library (tur tiešām ir viss, kas vajadzīgs)
Nekas sarežģīts principā tur nav. Viss jau arī atkarīgs kā tu tur gribi staigāt pa grafu. Daudzi apstaigāšanas algoritmi ir jau boosta graphā iekšā. Atliek tikai tos pareizi pielietot savām vajadzībām.
Bet ja nu gribi manuāli, tad to dara aptuveni šādi:

// orientēts grafa tips
typedef adjacency_list<vecS, vecS, directedS, std::string, int> Graph;

// virsotnes un šķautnes tips
typedef Graph::vertex_descriptor Node;
typedef Graph::edge_descriptor Edge;

Graph graph;

Node root = add_vertex(graph);
graph[root] = "root_dati";
Node i = root;

while (whatever)
{

   // iterē pa visiem i kaimiņiem
    BOOST_FOREACH(Edge edge, out_edges(i, graph))
    {
        Node j = target(edge, graph);
 
        // kautko dari virsotnei j
        // ...
    }
             
    Node new_node = add_vertex(graph);
    graph[new_node] = "jaunas nodes dati";
    Edge e = add_edge(i, new_node, graph).first; // pieliek šķautni no i uz new_node
    graph[e] = 666; // var protams neko nelikt šķautnes datos un tos tipā vispār nenorādīt, ja nevajag
}