离散实验报告.doc

《离散实验报告.doc》由会员分享，可在线阅读，更多相关《离散实验报告.doc（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实 验 报 告（2014 / 2015 学年 第 一 学期）课程名称离散数学实验名称图的随机生成及欧拉（回）路的确定实验时间2015年12月30日指导单位计算机科学与技术系指导教师张琳学生姓名崔新班级学号B学院(系)计软院专 业软嵌NIIT一、实验内容和要求对给定n个结点，随机生成邻接矩阵以确定某无向简单图并进行欧拉图和半欧拉图的判定，若符合则给出至少一条欧拉回路或欧拉路。三、程序源代码#include #include #include using namespace std;int map5555, n, m = 0; /图，节点数，边数，int ans50, cnt = 0; /记录欧拉

2、路的路径，路径数bool vis50; /标记点是否被访问int st; /判是否为连通图，搜索的起点struct stackint top, node100;s; /定点的栈结构void show() /输出随机生成的无向图关系矩阵for (int i = 0; i n; i+)for (int j = 0; j n; j+)cout mapij ;cout endl;void init() /初始化函数bool flag = false; /标记是否生成图memset(map, 0, sizeof(map);memset(vis, false, sizeof(vis);memset(ans

3、, 0, sizeof(ans);srand(unsigned)time(NULL);for (int i = 0; i n; i+)for (int j = i + 1; j n; j+)mapij = 0 + rand() % 2; /随机生成无向图for (int i = 0; i n; i+)for (int j = 0; j n; j+)if (mapij)flag = true; /最少有一条边m+; /记录边的条数mapji = 1; /无向图的定义st = i; /有一条边则其任意一个端点设为起点while (!flag)init();void DFS2(int x) /深度优

4、先搜索visx = true;for (int i = 0; i n; i+)if (!visi & mapxi)DFS2(i);/从所设定的起点深度优先遍历图，若有一个点没被访问，则为非连通图bool judge()DFS2(st);for (int i = 0; i n; i+)if (!visi)return false;return true;void DFS(int x) /深度优先搜索s.top+;s.nodes.top = x;for (int i = 0; i 0)mapix = 0; /删边操作mapxi = 0;DFS(i);break;void Fleury(int x)

5、 /Fleury算法int b;s.top = 0;s.nodes.top = x; /起点入栈while (s.top = 0)b = 0;for (int i = 0; i 0)b = 1;break;if (b = 0) /如果没有可扩展的点，则记录下该点并将其出栈anscnt+ = s.nodes.top + 1;s.top-;else /如果有，则将其出栈并继续搜索s.top-;DFS(s.nodes.top + 1);cout endl;void answer() /输出答案for (int i = 0; i cnt; i+)cout ansi ;cout endl;int mai

6、n()int num = 0, start = 0, degree; / 奇度顶点个数, 欧拉路的起点, 每个顶点的度cout n;init();cout 生成的无向图为: endl;show();if (!judge()cout 非连通图 endl;return 0;/如果存在奇度顶点，则从奇度顶点出发，否则从0出发for (int i = 0; i n; i+)degree = 0;for (int j = 0; j n; j+)degree += mapij;if (degree % 2)start = i;num+;/无向图具有一条欧拉路，当且仅当G是连通的，且有0个或2个奇数度结点if (num = 0 | num = 2)Fleury(start);/欧拉路径的头和尾相等，则说明欧拉路是回路if (ans0 = anscnt - 1)cout 该图为欧拉图，欧拉回路为: ;elsecout 该图为半欧拉图，欧拉路为: ;answer();elsecout 非欧拉图或半欧拉图 num;return 0;四、测试界面和用例五、实验中遇到的问题和解决方案六、实验体会