i wanted to check the connectivity of of graph...
i can use the disjoint data structure...but heard one can use multimaps...is it possible...
it ll be helpful if i am provided with an example or sample code...
thanks
Printable View
i wanted to check the connectivity of of graph...
i can use the disjoint data structure...but heard one can use multimaps...is it possible...
it ll be helpful if i am provided with an example or sample code...
thanks
Well, if you want the nodes of each connected set, yes. Use a standard simple disjoint subgraph finder (pretty trivial using any kind of search), and keep a counter that counts the number of subgraphs you've found. And, while you walk the graph, add each node to the multimap, using the current count as an index. When you're done, the multimap will contain one key per subgraph, and all the nodes of the subgraph will be mapped at this key.Quote:
but heard one can use multimaps
But since the key set is integral, 0-based and continuous, it intuitively sounds better to use a simple array/vector as the map, mapping to another container type.
http://www.boost.org/doc/libs/1_36_0...omponents.html
thanks for the reply..
i seem to partially understand ur statement...
say edges 1 2 and 3 4 ..means there are 2 components...graph is not connected...
for my scenario each vertex is a character
so i didCode:for each node
makeset(v)
for each edge :if(fibnset(u)!=findset(v)
union(u,v)
finally i check findset(all vertices)whether lie in same component ....if yes ,its ok ,,,,,else not connected
can u just explain with maps with a sample code
Do you understand how depth first visitation works? Given such a visitation function, you could write it as pseudo-code:
Code:multimap<int, vertex> components;
graph g;
int currentComponent = 0;
for every vertex v in g {
if v not marked {
visit_depth(v, visitor);
++currentComponent;
}
}
where visitor = function(vertex w) {
mark w;
insert w into components with key currentComponent;
}