[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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