Re: [igraph] how do you check for connectedness?

[Figa Pelosa]

thanks!

--- Mar 17/11/09, Tamas Nepusz <address@hidden> ha scritto:

> Da: Tamas Nepusz <address@hidden>
> Oggetto: Re: [igraph] how do you check for connectedness?
> A: "Help for igraph users" <address@hidden>
> Data: Martedì 17 novembre 2009, 10:08
> > I'm writing a little program in
> matlab and I'd need to check if a graph is connected.
> > What I do now is basically an iteration on the
> exponentiation of the adjacency matrix: I do that until two
> subsequent steps produce equal results and then I check if
> every node is connected to other nodes.
> > 
> > It's quite a slow tecnique, so I was wondering if in
> iGraph (which can do this check pretty fast) you use a
> different method.
> We use a breadth-first search starting from vertex zero and
> we keep track of the number of visited vertices (see 
> http://en.wikipedia.org/wiki/Breadth-first_search). If
> the BFS queue becomes empty and the number of visited
> vertices is less than the number of vertices in the graph,
> then there exists at least a single vertex which is not
> reachable from vertex zero, hence the graph is not
> connected. Otherwise it is connected (weakly).
> 
> -- 
> Tamas
> 
> 
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>