|
|
#define Graph_algdeclare(G,V,E)...
#define Graph_algimplement(G,V,E)...
Expanding Graph_algdeclare(G,V,E) produces the following text:
Set<G> strong_conn_comps(const G& g);
Set<G> conn_comps_u(const G& g);
A connected component is a Graph having the property that each Vertex is reachable from every other Vertex by following some path (sequence of Edges). If the Graph is being treated as undirected, Edge directionality is ignored in finding paths; if the Graph is being treated as directed, then Edge directionality is treated as significant in finding paths. By the above definition, every Graph (whether directed or undirected) consists of one or more components.
These functions take a Graph g and find its connected components. As usual, functions with the _u suffix treat the Graph as undirected, while functions without the suffix treat the Graph as directed.
O(max(v,e)), where v is the number of Vertices and e is the number of Edges in the Graph.