《离散实验报告四》由会员分享，可在线阅读，更多相关《离散实验报告四（9页珍藏版）》请在金锄头文库上搜索。
1、一、实验目的判断随机生成的邻接矩阵是否为欧拉图或欧拉半图，若是， 求取其欧拉回路或欧拉路。二、问题分析本实验的最终目的是要求取欧拉图的欧拉回路或欧拉半图的欧拉路，那么在这之前我们需要完成的是邻接矩阵的生成，图的连通性判别，如若连通，再判断其是否为欧拉图或欧拉半图，最终求取欧拉回路或欧拉路。1 .生成随机矩阵定义数组二维数组l叩，用以存储邻接矩阵的信息。再定义结点数目 n,从键盘键入之。根据n 的大小，在嵌套的for 循环中，每次循环都利用rand 函数随机生成某数并对2 取余， 将结果赋值给lij 。 当然在 for 循环之前需要调用srand函数取计算机当前时间作为种子，防止rand 函数生
2、成伪随机数。2 .判断连通性考虑到在上述步骤中已经有图的邻接矩阵生成，可以考虑用可达性矩阵来判断图的连通性。这样，问题的关键就变成了求取可达性矩阵的问题。为了不影响原邻接矩阵信息，定义新二维数组p 复制邻接矩阵数据来进行运算操作，并定义二维数组s ，初始化为全0，用来存储最终可达性矩阵。具体操作应为：首先将利用for 循环将 p 与 l 相乘，结果存于p 中；而后将p加上s,结果存于s中。冉将以上步骤整体置于一个循环 n次的for循环下。执行完之后，检查 s ， 将非零值都修正为1， 这样我们可以得到可达性矩阵s 。最后，遍历检查s 中每个元素的值，如果发现有元素值为0，那么该图不具有连通性；
3、否则，该图具有连通性，可以进行下面步骤的判断。3 .判断是否为欧拉图或欧拉半图定义数组deg， 用来存储每个结点的度。依行检查l ， 将第 i 行的值相加可得degi。再依据deg口来判断该图是否为欧拉图或欧拉半图：如果每个结点的度均为偶数，该图为欧拉图；如果奇数度结点个数为2， 该图为欧拉半图；否则，两者均不是。4 .欧拉路或欧拉回路的求取对于欧拉路或欧拉回路的求取，我们依旧利用邻接矩阵来求。（ 1）求取欧拉回路时，我们可以任意选择起点开始。按行搜索邻接矩阵，若果检查第i行时发现lij非0,将其修正为0后，输出i-j,搜索第j行，如此循环，可得欧拉回路。当然在此之前我们需要求得每个结点的度数
4、之和sum， 来控制上述循环次数不超过sum/2,使得循环可以适时结束( 2)在求取欧拉路时，只要控制循环起点为奇数度结点即可。其他步骤与上述求取欧拉回路步骤一致。三、具体程序实现#include #include #include using namespace std;int main()int n,l2020,p2020,s2020;int deg20;/用于存储每个结点的度数int count1=0;/用于存储奇数度结点个数int start=0;srand(int)time(0);coutn;for(int i=0;in;i+)for(int j=i;jn;j+)if(i=j)lij
5、=0;elselij=rand()%2;lji=lij;cout随机生成领接矩阵：endl;for(i=0;in;i+)degi=0;for(int j=0;jn;j+)(coutlij;)coutendl;)/通过可达性矩阵判断连通性for(i=0;in;i+)(for(int j=0;jn;j+)(pij=lij;sij=0;)for(int y=0;yn;y+)(for(i=0;in;i+)(for(int j=0;jn;j+)(sij+=pij;)for(i=0;in;i+)(for(int j=0;jn;j+)(for(int k=0;kn;k+)(pij+=pik*lkj;for(
6、i=0;in;i+)(for(int j=O;jn;j+)(if(siU!=O)(siU=1；)coutvv”可达性矩阵为：endl;for(i=0;in;i+)(for(int j=O;jn;j+)(coutsij) coutendl;)欧拉(半)图的判断和欧拉(回)路的的求取 int sum=0;for(i=0;in;i+)(for(int j=O;jn;j+)(if(liU=1) degi+;)for(i=0;in;i+)(count1+;start=i;)for(i=0;in;i+)(sum=sum+degi;)for(i=0;in;i+)(for(int j=0;jn;j+)(if(
7、sij=0)(cout”此图不连通endl;cout既不是欧拉图也不是欧拉半图endl;return 0;)int x=0;int j=100;cout此图连通endl;if(count1=0)(cout是欧拉图，欧拉回路如下：endl;for(i=0;xsum/2;i=j)(for(j=0;jj+1 endl;liU=O；IUi=O；x+;break;)else if(count1=2)(coutvv”是欧拉半图，欧拉路如下：endl;for(i=start;xsum/2;i=j)(for(j=0;jj+1 endl;liU=0；x+;break;)elsecoutvv”既不是欧拉图也不是欧拉半图endl;return 0;四、程序测试用例截图G:受序设计D ubug,离散实蜡四exe G:程序设计口 ebug离散实验四Exe11XG:程序设计Debug离散实验四exe，像机生成领痛楚阵：0 0 110 0 11110 0110 0可达性矩阵为：1111111111111111叱图连通愿嵌拉国，欧拉回路如下：1-33-22-4卜1Press any key to continue
