igraph-help
[Top][All Lists]

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

 From: Tamas Nepusz Subject: Re: [igraph] how do you check for connectedness? Date: Tue, 17 Nov 2009 10:08:10 +0000

```> 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

```