# Connected graph given adjacency matrix

75 views (last 30 days)

Show older comments

Hi all, I'm working on a research project on graphical models involving a large dimension (large number of nodes). I'm just wondering, is there an existing efficient algorithm to determine whether the graph is connected or not given its adjacency matrix? I've tried looking but it seems that the existing ones are brute force algorithms which are costly. Does MATLAB have a built-in function? When I checked, it seems that none exists as of now.

Help would be greatly appreciated!

##### 0 Comments

### Accepted Answer

Wolfgang Schwanghart
on 29 May 2012

You can use the function dmperm to see if a graph consists of one or several connected components. E.g. see the example here http://blogs.mathworks.com/steve/2007/03/20/connected-component-labeling-part-3/

HTH, W.

### More Answers (3)

Christine Tobler
on 22 Dec 2016

Edited: Christine Tobler
on 22 Nov 2019

I realize this is an old question, but since it's still getting visits, I have a small addition. As of R2015b, the new graph and digraph classes have a method for computing connected components. To check whether a graph is connected based on its adjacency matrix A, use

g = digraph(A);

bins = conncomp(g, 'Type', 'weak');

isConnected = all(bins == 1);

The vector bins gives the bin number for each node of A. If a graph is connected, all nodes will be in one bin, which is checked using all(bins == 1). This is not necessarily faster than dmperm, but easier to read.

##### 2 Comments

Christine Tobler
on 22 Nov 2019

Hon Wah Yeung
on 31 Jan 2021

This will work if you can at least load the matrix (meaning the matrix is not larger than the max possible array for Matlab) to Matlab.

function [idx,Group] = CheckConnected(E)

L=length(E);

T=find(E(:,1)~=0);

T=[T;1]';

M=sum(E(:,T),2);

T1=union(find(M~=0),T);

while length(T1)>length(T)

T=T1;

M=sum(E(:,T),2);

T1=union(find(M~=0),T);

end

if length(T)==L

idx=1;

Group=T;

else

idx=0;

Group=T;

end

end

##### 0 Comments

### See Also

### Categories

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!