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 depthfirst or breadthfirst 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.speranza79@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
Email address: squarcel@dia.uniroma3.it
Phone: +390657333215
Fax: +390657333612
http://www.dia.uniroma3.it/~squarcel

To unsubscribe, email: devunsubscribe@commons.apache.org
For additional commands, email: devhelp@commons.apache.org
