Hello,
On 27/01/2012 12:35, Marco Speranza wrote:
Hi all,
I'm trying to implement the Boruvka's algorithm and I need to know is a
grah is connected or not.
So I'd like to propose a simple algorithm to do that.
A simple way to implement that is run a depth-first or breadth-first search
starting from an arbitrary vertex. If the number of the vertices touched
are the same of the origina graph, the graph is connected.
cool, go for it :-)
Moreover the algorithm could count the number of che "connected componet" (
http://en.wikipedia.org/wiki/Connected_component_(graph_theory).
well you get that number if you actually map each vertex to a connected
component, which means you could need to run the search algorithm more
than once.
As a unified solution maybe we could go for an algorithm that returns
the connected components as a collection of graphs, and then in your
case you just check that there is only one connected component.
Ciao
Claudio
what do you think about that?
Ciao
--
Marco Speranza<marco.speranz...@gmail.com>
Flick photostream: http://www.flickr.com/photos/marcosperanza79/
Google Code: http://code.google.com/u/marco.speranza79/
--
Claudio Squarcella
PhD student at Roma Tre University
E-mail address: squar...@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~squarcel
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
