commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Marco Speranza <marco.speranz...@gmail.com>
Subject [Graph] Graph connectivity algo
Date Fri, 27 Jan 2012 11:35:26 GMT
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.

Moreover the algorithm could count the number of che "connected componet" (
http://en.wikipedia.org/wiki/Connected_component_(graph_theory).

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/

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message