commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Claudio Squarcella <squar...@dia.uniroma3.it>
Subject Re: [Graph] Graph connectivity algo
Date Fri, 27 Jan 2012 11:47:24 GMT
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.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
E-mail address: squarcel@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~squarcel


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message