clear;
clc;
%输入邻接矩阵
disp('--------图的连通性以及连通分支数的判断--------');
N=input('请输入矩阵阶数：N=');%矩阵大小N*N
%随机产生一个阶数为N的邻接矩阵
select=[0:1];
A=zeros(N,N);
for i1=1:N
for j1=1:i1;
if i1==j1
A(i1,j1)=0;
else
b=randperm(length(select));
A(i1,j1)=select(b(1));
A(j1,i1)=A(i1,j1);
end
end
end
%矩阵幂算法
tic;
n=size(A,1);%邻接矩阵阶数
P=zeros(n,n);%构造连通矩阵P
k=1;
for k=1:n %计算矩阵幂的和
A1=A^k;
P=P+A1;
end
S=n-rank(P);%连通分支数为0特征值个数
%计算矩阵幂算法运行时间
disp('矩阵幂算法运行时间'),toc;
%Warshell算法
tic;
S1=0;a=1;
G=zeros(n,1);
for i=1:n
for j=(i+1):n
if A(i,j)==1%若两端之间有边连通
if G(i)==G(j)%若两端之间有连通链，说明二者在同一连通分支
if G(i)==0
G(i)=a;G(j)=a;
a=a+1;
S1=S1+1;
end
else
if G(i)==0
G(i)=G(j);%若与i不连通，则与j在同一连通分支
elseif G(j)==0
G(j)=G(i);%若与j不连通，则与i在同一连通分支
else%若两端相连通，但标记在不同连通分支，合并两连通分支
for b=1:n
if G(b)==G(i)
G(b)=G(j);%合并两连通分支
end
end
S1=S1-1;%合并两连通分支
end
end
end
end
end
%计算Warshell算法运行时间
disp('Warshell算法运行时间'),toc;
%输出结果
A
if S==1
disp('矩阵幂算法：Connected');
else
disp(['矩阵幂算法:Not Connected，连通分支数:',num2str(S)]);
end
if S1==1
disp('Warshell算法：Connected');
else
disp(['Warshell算法：Not Connected，连通分支数:',num2str(S)]);
end
