(word完整版)图的连通性判断matlab实验报告.doc

(word完整版)图的连通性判断matlab实验报告
(word完整版)图的连通性判断matlab实验报告
(word完整版)图的连通性判断matlab实验报告
实验三:图的连通性判断
一、实验目的
用计算机语言编写图的连通性判断算法，可输入图的邻接矩阵，判断图是否连通以及确定连通分支的个数,掌握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(’请输入图的邻接矩阵（格式如:[110;111；011］)C=’);
%矩阵幂算法
n=size（C,1）;％邻接矩阵阶数
P=zeros（n，n);%构造连通矩阵P
k=1；
fork=1:n ％计算矩阵幂的和
C1=C^k;
P=P+C1；
end
S=n—rank(P);％连通分支数为0特征值个数
%Warshell算法
S1=0；a=1;
G=zeros(n,1)；
fori=1:n
forj=（i+1)：n
ifC(i,j）==1%若两端之间有边连通
ifG(i）==G(j)%若两端之间有连通链，说明二者在同一连通分支
ifG(i)==0
G(i）=a；G（j)=a；
a=a+1；
S1=S1+1;
end
else
ifG（i)==0
G（i)=G(j);%若与i不连通,则与j在同一连通分支
elseifG(j）==0
G（j）=G(i）；％若与j不连通，则与i在同一连通分支
else％若两端相连通，但标记在不同连通分支,合并两连通分支
forb=1：n
ifG（b)==G(i）
G（b)=G（j）；%合并两连通分支
end
end
S1=S1-1;％合并两连通分支
end
end
end
end
end
％输出结果
C
ifS==1
disp('矩阵幂算法：连通’）;
else
disp(［’矩阵幂算法:不连通,连通分支数=’,num2str(S）])；
end
ifS1==1
disp('Warshell算法:连通’）；
else
disp（['Warshell算法：不连通，连通分支数=’，num2str（S1）]);
end
五、数据结构
1.主要函数
输入函数：
C=input（'输入图的邻接矩阵C=')；
矩阵幂算法：
n=size（C，1）；％邻接矩阵阶数
P=zeros(n,n）;%连通矩阵P
k=1;
fork=1:n％计算矩阵幂的和
C1=C^k；
P=P+C1；
end
S=n-rank(P)；%连通分支数为0特征值个数
Warshell算法：
S1=0；a=1；
G=zeros（n,1）;
fori=1:n
forj=（i+1):n
ifC（i，j）==1%若两端之间有边连通
ifG（i)==G（j）％若两端之间有连通链,说明二者在同一连通分支
ifG(i）==0
G（i)=a;G(j)=a;
a=a+1；
S1=S1+1;
end
else
ifG（i）==0
G(i)=G(j)；％若与i不连通，则与j在同一连通分支
elseifG（j)==0
G(j)=G（i）；％若与j不连通，则与i在同一连通分支
else%若两端相连通，但标记在不同连通分支,合并两连通分支
forb=1:n
ifG（b）==G（i）
G(b）=G(j）;％合并两连通分支
end
end
S1=S1—1；％合并两连通分支
end
end
end
end
end
输出函数：
C
ifS==1
disp('矩阵幂算法：连通')；
else
disp（['矩阵幂算法：不连通，连通分支数=’，num2str（S）］）；
end
ifS1==1
disp（’Warshell算法:连通’）;
else
disp（［’Warshell算法：不连通,连通分支数=',num2str(S1)］);