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

[Tamas Nepusz]

> 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