图的连通性判断matlab实验报告.doc

实验三：图的连通性判断
一、实验目的
用计算机语言编写图的连通性判断算法，可输入图的邻接矩阵，判断图是否连通以及确定连通分支的个数，掌握Warshell算法或矩阵幂算法的实现方法。

二、实验原理
1、Warshell算法
Warshell算法可解决图是否连通的问题, 而且效率很高。在该算法中，矩阵是判断矩阵，表示从到连通，表示从到不连通。
(1)置新矩阵 P:= C;
(2)置 = 1;
(3)对所有的,若, 则对k=1,2,…,n, 有;
(4) ;
(5) 如转向步骤(3), 否则停止。
2、矩阵幂算法
由于邻接阵包含了图的所有信息，和关联阵一样，是图的等价表示。可以通过对邻接阵C做一些计算，得到图G的一些性质。例如考虑中的的元素，如果它不为零，由于，则至少存在一组或一个长度为3的链使端和端相连。从而，通过计算C的各阶幂次可得到关于图是否连通的信息。

三、实验内容
1.利用MATLAB等语言实现图的连通性判断算法，可对输入的邻接阵进行连通性以及连通分支数的判断。
2.比较Warshell算法和矩阵幂算法在算法正确性和算法复杂度上的区别。
3.对算法进行优化。
四、采用的语言
MatLab
源代码：
clear,clc;
%输入邻接矩阵
disp('图的连通性以及连通分支数的判断');
C = input('请输入图的邻接矩阵(格式如：[1 1 0;1 1 1;0 1 1]) C=');
%矩阵幂算法
n=size(C,1);%邻接矩阵阶数
P=zeros(n,n);%构造连通矩阵P
k=1;
for k=1:n %计算矩阵幂的和
C1=C^k;
P = P + C1;
end
S=n-rank(P);%连通分支数为0特征值个数
%Warshell算法
S1=0;a=1;
G=zeros(n,1);
for i=1:n
for j=(i+1):n
if C(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
%输出结果
C
if S==1
disp('矩阵幂算法：连通');
else
disp(['矩阵幂算法:不连通，连通分支数=',num2str(S)]);
end
if S1==1
disp('Warshell算法：连通');
else
disp(['Warshell算法：不连通，连通分支数=',num2str(S1)]);
end
五、数据结构
1.主要函数
输入函数：
C = input('输入图的邻接矩阵C=');
矩阵幂算法：
n=size(C,1);%邻接矩阵阶数
P=zeros(n,n);%连通矩阵P
k=1;
for k=1:n %计算矩阵幂的和
C1=C^k;
P = P + C1;
end
S=n-rank(P);%连通分支数为0特征值个数
Warshell算法：
S1=0;a=1;
G=zeros(n,1);
for i=1:n
for j=(i+1):n
if C(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
输出函数：
C
if S==1
disp('矩阵幂算法：连通');
else
disp(['矩阵幂算法：不连通，连通分支数=',num2str(S)]);
end
if S1==1
disp('Warshell算法：连通');
else
disp(['Warshell算法：不连通，连通分支数=',num2str(S1)]);
end
2. 算法的流程图
矩阵幂算法：
Yes
No
C1=C^k
P=P+C1
k=k+1
得到C的阶数n
k=1
开始
输入邻接矩阵C
k<=n?
连通分支数S=n-连通矩阵P的秩
结束

Warshell算法：

i++
若p(j,i)=1
p(i,j)=p(i,k)+*p(k,j)
j++
i=1,j=1
输入邻接矩阵C
得到C的阶数n
边数m
k=1
开始

i<=n?
j<=i?
Yes
No
Yes
No
结束
连通分支数S

六、实验结论与分析

Warshell算法和矩阵幂算法在算法正确性基本相同，
算法复杂度上矩阵幂算法比Warshell算法复杂的多。
矩阵幂算法复杂度为O(nn)
Warshell算法复杂度为O(n3)

七、遇到的问题及解决方法
在编程初期，对两种算法的理解不够，在编程时无从下手，复习课本后并在网上查找了相关资料，对两种算法的核心有了较深的理解，编程时就没有问题了。

八、实验心得
通过本次实验实现了用计算机语言编写图的连通性判断算法，基本掌握了矩阵幂算法和Warshell算法的实现方法，对MatLab编程语言更加熟悉，培养了算法设计与优化能力。此次实验我受益匪浅。