离散数学实验四
6页1、实 验 报 告(2014 / 2015 学年 第 一 学期)课程名称离散数学实验名称图的随机生成及欧拉(回)路的确定实验时间2014年12月12日指导单位南京邮电大学指导教师罗卫兰学生姓名沈一州班级学号B12040920学院(系)计算机软件学院专 业NIIT(软嵌)实 验 报 告实验名称图的随机生成及欧拉(回)路的确定指导教师罗卫兰实验类型验证型实验学时4实验时间12.12一、 实验目的和要求内容:编程随机生成n个结点的无向图并能进行(半)欧拉图的判定,若是则给出欧拉(回)路。要求:对给定n个结点,随机生成邻接矩阵以确定某无向简单图并进行欧拉图和半欧拉图的判定,若符合则给出至少一条欧拉回路或欧拉路。二、 实验环境(实验设备)硬件: CPU:3.0Ghz 内存:1.00GB软件:操作系统:Windows XP SP3编程软件:Visual C+ 6.0三、 实验原理及内容总体思想:这次题目要求是根据随机生成的图求欧拉(回)路,先要随机生成一个邻接矩阵,然后判定是否是欧拉回路只要根据奇数度结点的个数。再用一个递归函数找出欧拉路。核心代码:1、根据结点数生成邻接矩阵:for(i=0;in;i
2、+)for(j=0;jj) /边没有方向性aij=aji;else /随机赋值,0代表没有边,1代表有边aij=rand()%2;cout ; /输出该邻接矩阵for(i=0;in;i+)cout i+1;coutendl;for(i=0;in;i+)couti+1;for(j=0;jn;j+)cout aij;coutendl;2、根据奇数度结点数判定是否含有欧拉(回)路:odd=0;for(i=0;in;i+)count=0;for(j=0;jn;j+)count+=aij; /统计每个结点的度数if(count%2=1)odd+; /若为奇数,则总数+1if(odd=0)cout该图没有奇数度结点,具有欧拉回路,是欧拉图。endl;else if(odd=2)cout该图有两个奇数度结点,具有欧拉路,是半欧拉图。endl;elsecout该图奇数度结点的个数为odd,所以不具有欧拉路。endl;3、半欧拉图中找出奇数度结点标号:flag1=flag2=-1; /分别代表两个奇数度结点的标号for(i=0;in;i+)count=0;for(j=0;jn;j+)count+=aij
3、;if(count%2=1)if(flag1=-1)flag1=i+1;elseflag2=i+1;4、求欧拉(回)路:void find(int found,int time)int i,j,flag;for(i=0;in;i+)if(afoundi=1)flag=0;for(j=0;jtime;j+) /表示是否已经存在if(bj=i)flag=1;break;if(!flag)btime=i;time+;if(timeexist) /如果还没走完find(i,time); /递归elsereturn;四、运行结果:首先是输入结点数:然后随机打印出邻接矩阵:根据性质判断并求出欧拉图:再试3次:实 验 报 告五、实验小结这次题目要求是根据随机生成的图求欧拉(回)路,首先难点是如何随机生成一个图,这要考虑到3个细节:第1个是同一个结点之间没有边,第2个就是这是无向图,一旦一个结点有了一条边,对应的另一个结点也要有一条边,第3个是要考虑到孤立结点。在此基础上生成了邻接矩阵,欧拉图判断就好弄多了,只要判断奇数度结点的个数。然后再用递归函数找到一条可行路即可。通过这次实验,加深了我对图的相关知识的理解,也提高了我动手编程的能力。五、指导教师评语 成 绩批阅人日 期- 5 -
《离散数学实验四》由会员小**分享,可在线阅读,更多相关《离散数学实验四》请在金锄头文库上搜索。
2020年高考真题——理科综合(全国卷Ⅲ)+Word版含答案
2021年绝味鸭脖策划书
2021年熟食店创业方案
2021年熟食店开店策划
2021年卤菜店创业计划书
2021年周黑鸭网络营销策划方案
东大21年1月考试《现代设计方法》考核作业
谈我国行政管理效率的现状及其改观对策(论文)
单证员考试-备考辅导-复习资料:无贸易背景信用证案分析.docx
土木工程毕业生答辩自述.docx
建筑学毕业后工作状态真实写照.doc
C#代码规范(湖南大学).doc
xx区食药监局2019年工作总结及2020年工作计划
2019年中医院药物维持治疗门诊工人先锋号先进事迹
2019年度xx乡镇林长制工作总结
2019年性艾科工作计划书
2019年人才服务局全国扶贫日活动开展情况总结
关于组工信息选题的几点思考
摘了穷帽子 有了新模样
2019年某集团公司基层党支部书记培训班心得体会
2024-04-08 33页
2024-04-08 10页
2024-04-08 25页
2024-04-08 12页
2024-04-08 10页
2024-04-08 21页
2024-04-08 40页
2024-04-08 34页
2024-04-08 28页
2024-04-08 28页