jk.rar_图 连通_连通_连通分支_连通图

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