commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Claudio Squarcella <>
Subject Re: [Graph] Graph connectivity algo
Date Fri, 27 Jan 2012 11:47:24 GMT

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" (

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.


> what do you think about that?
> Ciao
> --
> Marco Speranza<>
> Flick photostream:
> Google Code:

Claudio Squarcella
PhD student at Roma Tre University
E-mail address:
Phone: +39-06-57333215
Fax: +39-06-57333612

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message