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

- 02-04-2009dppDisjoint set
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 - 02-04-2009CornedBeeQuote:

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 - 02-04-2009dpp
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 - 02-04-2009CornedBee
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;

}