Connected graph given adjacency matrix

21 次查看（过去 30 天）
imperial1991
imperial1991 2012-5-29
回答： Hon Wah Yeung 2021-1-31
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!

请先登录，再回答此问题。

采纳的回答

Wolfgang Schwanghart
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.

更多回答（3 个）

Christine Tobler
Christine Tobler 2016-12-22
编辑：Christine Tobler 2019-11-22
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 个评论
Jonathan DuBois
Jonathan DuBois 2017-8-24
What is the point of the first command? Should it be: bins = conncomp(g, 'Type', 'weak')? It works with g in the second command but with A, I get the following error: Undefined function 'conncomp' for input arguments of type 'double'.
Christine Tobler
Christine Tobler 2019-11-22
Thank you, yes, this was a typo. I've edited the original answer to fix this (although it took me two years to realize you had commented on this answer).

请先登录，再进行评论。

Andrei Bobrov
Andrei Bobrov 2012-5-29
try grTheory - Graph Theory Toolbox by Sergii Iglin
  1 个评论
imperial1991
imperial1991 2012-5-30
hi andrei, it seems like there's no function for checking whether a graph is connected or not. thanks anyway!

请先登录，再进行评论。

Hon Wah Yeung
Hon Wah Yeung 2021-1-31
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

类别

在 Help Center 和 File Exchange 中查找有关 Directed Graphs 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by