求图的连通性,8.doc

“离散数学”实验报告（求图的连通性）专 业 网络工程 班 级 1202班 学 号 12407442 姓 名 张敏慧 2013.12.14目录一.实验目的3二.实验原理31. Warshell算法 32. 矩阵幂算法3三.实验环境3四. 实验流程图31.实验内容32.实验流程图4五.实验代码51.MATLAB语言.52.C语言7六. 实验结果8 七. 实验总结9一、实验目的用计算机语言编写图的连通性判断算法，可输入图的邻接矩阵，判断图是否连通以及确定连通分支的个数，掌握Warshell算法或矩阵幂算法的实现方法。二、实验原理1、Warshell算法Warshell算法可解决图是否连通的问题, 而且效率很高。在该算法中，矩阵是判断矩阵，表示从到连通，表示从到不连通。(1)置新矩阵 P:= C;(2)置 = 1; (3)对所有的,若, 则对k=1,2,n, 有;(4) ;(5) 如转向步骤(3), 否则停止。2、矩阵幂算法由于邻接阵包含了图的所有信息，和关联阵一样，是图的等价表示。可以通过对邻接阵C做一些计算，得到图G的一些性质。例如考虑中的的元素，如果它不为零，由于，则至少存在一组或一个长度为3的链使端和端相连。从而，通过计算C的各阶幂次可得到关于图是否连通的信息。三、实验环境使用visual C+6.0为编程软件，采用C语言为编程语言实现。使用MATLAB等语言实现图的连通性判断算法。四、实验流程图实验内容：利用MATLAB等语言实现图的连通性判断算法，可对输入的邻接阵进行连通性以及连通分支数的判断。实验流程图矩阵幂算法：YesNoC1=CkP=P+C1k=k+1得到C的阶数nk=1开始输入邻接矩阵Ck=n?连通分支数S=n-连通矩阵P的秩结束Warshell算法：i+若p(j,i)=1p(i,j)=p(i,k)+*p(k,j)j+i=1,j=1输入邻接矩阵C得到C的阶数n边数mk=1开始i=n?j=i?YesNoYesNo结束连通分支数S五、实验代码MatLab 源代码：clear,clc;%输入邻接矩阵disp(图的连通性以及连通分支数的判断);C = input(请输入图的邻接矩阵(格式如：1 1 0;1 1 1;0 1 1) C=);%矩阵幂算法n=size(C,1);%邻接矩阵阶数P=zeros(n,n);%构造连通矩阵Pk=1;for k=1:n%计算矩阵幂的和 C1=Ck; P = P + C1;endS=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 endend%输出结果Cif S=1 disp(矩阵幂算法：连通);else disp(矩阵幂算法:不连通，连通分支数=,num2str(S);endif S1=1 disp(Warshell算法：连通);else disp(Warshell算法：不连通，连通分支数=,num2str(S1);endC语言1.主要函数输入函数：C = input(输入图的邻接矩阵C=);矩阵幂算法：n=size(C,1); %邻接矩阵阶数P=zeros(n,n); %连通矩阵Pk=1;for k=1:n %计算矩阵幂的和 C1=Ck; P = P + C1;endS=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 endend输出函数：Cif S=1 disp(矩阵幂算法：连通);else disp(矩阵幂算法：不连通，连通分支数=,num2str(S);endif S1=1 disp(Warshell算法：连通);else disp(Warshell算法：不连通，连通分支数=,num2str(S1);end六、实验结果Warshell算法和矩阵幂算法在算法正确性基本相同，算法复杂度上矩阵幂算法比Warshell算法复杂的多。矩阵幂算法复杂度为O(nn)Warshell算法复杂度为O(n3)七、实验总结在编程初期，对两种算法的理解不够，在编程时无从下手，复习课本后并在网上查找了相关资料，对两种算法的核心有了较深的理解，编程时就没有问题了。这