《图随机生成与欧拉(回)路确定》由会员分享，可在线阅读，更多相关《图随机生成与欧拉(回)路确定（34页珍藏版）》请在金锄头文库上搜索。
1、实 验 报 告（ / 学年 第 一 学期）课程名称离散数学实验名称图的随机生成及欧拉(回)路的确定实验时间年月日指导单位指导教师学生姓名班级学号学院(系)专 业 实 验 报 告实验名称图的随机生成及欧拉(回)路的确定指导教师实验类型上机实验实验学时4实验时间一、 实验目的和要求目的：编程随机生成n个结点的无向图或者有向图并能判定该无向图或者有向图是否存在欧拉(回)路，若是则给出欧拉（回）路。要求：对给定n个结点，随机生成邻接矩阵以确定某无向或者有向简单图并进行是否存在欧拉(回)路的判定，若符合则给出至少一条欧拉回路或欧拉路。二、实验环境(实验设备)硬件:PC机。软件:Code:Blocks （
2、C+ ）三、实验原理及内容内容：图的随机生成：首先由用户选择是生成无向图还是有向图，再读入用户输入的结点个数，然后调用对应的无向图类或者有向图类的构造函数，在构造函数中随机生成邻接矩阵，计算可达性矩阵并且输出这两种矩阵。欧拉(回)路的确定：调用对应的无向图类或者有向图类中的判定是否存在欧拉路的函数和判定是否存在欧拉回路的函数，如果存在，输出欧拉(回)路存在，并且调用遍历欧拉路或者欧拉回路的函数。 原理：建立一个图类(父类)，在图类中用n储存结点个数，用*a指向一个二维数组存储邻接矩阵，用*p指向的二维数组储存可达性矩阵，建立图类的构造函数、析构函数、输出邻接矩阵的函数、输出可达性矩阵的函数、判
3、断是否连通的函数。由于两种图中的判断是否存在欧拉(回)路的原理不同，所以建立图类的两个派生类无向图类和有向图类，在类中分别建立各自的判断是否存在欧拉(回)路的函数，以及遍历欧拉(回)路的函数。这些函数的原理就是欧拉(回)路判定的充要条件，结合邻接矩阵和可达性矩阵的特点编写即可。 程序：#include #include #include #include using namespace std;class graph/图类protected: int n;/结点数 int *a;/储存邻接矩阵 int *p;/储存可达性矩阵public: graph(int size); graph(); v
4、oid Print_linjie();/输出邻接矩阵 void Print_keda();/输出可达性矩阵 bool Liantong_or_not();/判断图是否连通;graph:graph(int size) n=size; srand(time(NULL); a=new int*n; for(int i=0;in;i+) ai=new intn; for(int j=0;ji;j+) aij=aji=rand()%2; aii=0; p=new int*n; for(int i=0;in;i+) pi=new intn; for(int j=0;jn;j+) pij=0; graph:
5、graph() for(int i=0;in;i+) delete ai; delete a; for(int i=0;in;i+) delete pi; delete p;void graph:Print_linjie() for(int i=0;in;i+) for(int j=0;jn;j+) coutaij ; coutendl; coutendl;void graph:Print_keda() for(int i=0;in;i+) for(int j=0;jn;j+) coutpij ; coutendl; coutendl;bool graph:Liantong_or_not()
6、for(int i=0;in;i+) for(int j=0;jn;j+) if(i!=j&pij=0) return false; return true;class Ygraph:public graph /有向图类public: Ygraph(int size); Ygraph() bool Oulalu_or_not(int &begin);/判断有向图是否存在单向欧拉路 bool Oulahuilu_or_not();/判断有向图是否存在单向欧拉回路 void DFS(int begin);private: void DFS(int begin,int k,bool *visit);
7、Ygraph:Ygraph(int size):graph(size) srand(time(NULL); for(int i=0;in;i+) for(int j=0;jn;j+) this-aij=rand()%2; this-aii=0; for(int i=0;in;i+) for(int j=0;jn;j+) if(this-aij=1) for(int k=0;kn;k+) if(this-aik|this-ajk) pik=1; bool Ygraph:Oulahuilu_or_not() if(!Liantong_or_not() return false; for(int i
8、=0;in;i+) int count1=0,count2=0; for(int j=0;jn;j+) if(this-aij) count1+; if(this-aji) count2+; if(count1!=count2) return false; return true;bool Ygraph:Oulalu_or_not(int &begin) if(!Liantong_or_not() return false; int count=0; int *r=new intthis-n;/储存入度与初度不同的结点的出度 int *s=new intthis-n;/储存入度与初度不同的结点
9、的入度 for(int i=0;in;i+) int count1=0,count2=0; for(int j=0;jn;j+) if(this-aij) count1+; if(this-aji) count2+; if(count1!=count2) rcount=count1; scount=count2; if(count1count2) begin=i; count+; if(count!=2) return false; else if(r0-s0=1&s1-r1=1|s0-r0=1&r1-s1=1) return true; else return false; void Ygraph:DFS(int
