_mario.lat said:
kruskal:minimum spanning tree. how to do?
Just do it! Kruskals algorithms is actually pretty simple. You just get a
list of all edges with their weights and 'std::sort()' them (especially for
graphs with high densities it is heuristically often benefitial to only
partially sort the edges and get an order on the next 10% or so of the
edges: typically you get a spanning tree out of only a fraction of all
edges). The interesting thing is only the union/find data structure which
is also extremely simple: just store a pointer to the representing node
with each node, initialize it to '0' and update it at the correct strategic
points.
There is a code (in C++) written?
The Boost Graph Library (see <
http://www.boost.org/>) provides a generic
implementation, i.e. one operating on arbitrary representations of the
graph. You just need to supply the entities abstracting the data structure,
i.e. some iterators and property maps - or use one of the sample graph data
structures also provided.
which contenitor do you suggest (Vector, set, ...)?
(s/contenitor/container/, I guess) Who cares? Use whatever is appropriate
to your situation. The idea of generic algorithms is to operate on any
reasonable representation and this certainly applies to the BGL
implementation.
