图的随机生成及欧拉回路的确定讲解.docx
《图的随机生成及欧拉回路的确定讲解.docx》由会员分享,可在线阅读,更多相关《图的随机生成及欧拉回路的确定讲解.docx(15页珍藏版)》请在冰点文库上搜索。
![图的随机生成及欧拉回路的确定讲解.docx](https://file1.bingdoc.com/fileroot1/2023-7/22/0f76cd42-b821-464d-949f-ee7e765dfc30/0f76cd42-b821-464d-949f-ee7e765dfc301.gif)
图的随机生成及欧拉回路的确定讲解
《离散数学》实验报告
(2015/2016学年第一学期)
题目:
图的随机生成及欧拉(回)路的确定
专业信息安全
学生姓名
班级学号
指导教师
指导单位计算机学院计算机科学与技术系
日期2015年12月29日
图的随机生成及欧拉(回)路的确定
一、实验内容和要求
内容:
编程随机生成n个结点的无向图并能进行(半)欧拉图的判定,若是则给出欧拉(回)路。
要求:
对给定n个结点,随机生成邻接矩阵以确定某无向简单图并进行欧拉图和半欧拉图的判定,若符合则给出至少一条欧拉回路或欧拉路。
2、实验目的
对给定n个结点,随机生成邻接矩阵以确定某无向简单图并进行欧拉图和半欧拉图的判定,若符合则给出至少一条欧拉回路或欧拉路。
三、实验任务
1、输入结点个数据生成随机图
2、进行(半)欧拉图的判定
3、若是则给出欧拉(回)路。
四、实验内容
#include
#include
#include
usingnamespacestd;
classEuler
{
public:
Euler(intnum);
~Euler();
voidDFS(intbegin);//公有的深度优先搜索函数
voidinputEdge();//输入边
voidPrintAM();//打印邻接矩阵
voidPrintRM();//打印可达性矩阵
voidWarshall();//Warshall算法求可达性矩阵
boolIsConnected();//判断图是否连通
intIsEorSE();//判断图是欧拉图还是半欧拉图
boolisEuler;
private:
voidDFS(intu,intv,bool**visited);//私有的深度优先搜索函数
intn;
int**a;//定义动态二维数组
int**p;//定义可达性矩阵
int*b;//存储每个结点的度数
};
Euler:
:
Euler(intnum)//构造函数
{
isEuler=false;
n=num;
inti,j;
a=newint*[n];
for(i=0;i{
a[i]=newint[n];
for(j=0;ja[i][j]=0;
}
p=newint*[n];
for(i=0;i{
p[i]=newint[n];
for(j=0;jp[i][j]=0;
}
b=newint[n];
for(i=0;ib[i]=0;
}
Euler:
:
~Euler()//析构函数
{
inti;
for(i=0;idelete[]a;
for(i=0;idelete[]p;
delete[]b;
}
voidEuler:
:
inputEdge()
{
srand((unsigned)time(NULL));
for(inti=0;i{
for(intj=i+1;j{
a[i][j]=0+rand()%2;//随机生成无向图
a[j][i]=a[i][j];
}
}
for(intii=0;ii{
for(intjj=0;jj{
if(a[ii][jj]==1)
{
p[ii][jj]=1;
p[jj][ii]=1;
}
}
}
}
voidEuler:
:
PrintAM()
{
cout<<"随机生成的图为:
"<for(inti=0;i{
for(intj=0;jcout<cout<}
}
voidEuler:
:
Warshall()
{
for(inti=0;ifor(intj=0;jif(p[j][i]==1)
{
for(intk=0;k{
if(p[j][k]+p[i][k]>0)
p[j][k]=1;
}
}
}
voidEuler:
:
PrintRM()
{
cout<<"可达性矩阵:
"<for(inti=0;i{
for(intj=0;jcout<
cout<}
}
boolEuler:
:
IsConnected()
{
inti,j;
boolflag=true;//flag标记是否连通
for(i=0;i{
for(j=0;jif(p[i][j]==0)//如果可达性矩阵中有一个元素为0,
{//就跳出循环,表示该图不连通
flag=false;
break;
}
if(!
flag)
break;
}
if(!
flag)
cout<<"该图不是连通的";
else
{
for(i=0;ifor(j=i;j{
if(a[i][j]==1&&i!
=j)//由边计算结点的度数
{
b[i]++;b[j]++;
}
}
}
returnflag;
}
intEuler:
:
IsEorSE()
{
inti,count=0,begin=-1;
cout<<"每个结点的度数:
"<for(i=0;icout<
"<
for(i=0;iif(b[i]%2!
=0)
{
count++;
begin=i;//初始化开始结点,存在奇数结点,则将其中一个作为开始点
}
if(begin==-1)//不存在奇数结点则将0作为起始点
begin=0;
if(count==2)
{
cout<<"该图是半欧拉图"<}
elseif(count==0)
{
cout<<"该图是欧拉图"<}
returnbegin;
}
voidEuler:
:
DFS(intbegin)
{
inti,j;
bool**visited=newbool*[n];//二维数组记录每条边是否被访问过
for(i=0;i{
visited[i]=newbool[n];
for(j=0;jif(a[i][j]==1)
visited[i][j]=false;
else
visited[i][j]=true;
}
for(j=0;jif(!
visited[begin][j])
{
DFS(begin,j,visited);
cout<}
for(i=0;idelete[]visited;
}
voidEuler:
:
DFS(intu,intv,bool**visited)
{
if(!
visited[u][v])//判断边是否访问过
{
visited[u][v]=true;visited[v][u]=true;//标记被访问
for(inti=0;iDFS(v,i,visited);
cout<}
}
intmain()
{
intn,m,begin;
boolflag;
cout<<"输入结点个数:
";
cin>>n;
Eulereuler(n);
euler.inputEdge();
euler.PrintAM();
euler.Warshall();
euler.PrintRM();
flag=euler.IsConnected();
if(flag)
{
begin=euler.IsEorSE();
if(euler.isEuler)
{
cout<<"具体路径为:
";
euler.DFS(begin);
}
}
cout<return0;
}
五、测试数据及其结果分析
6、调试过程中的问题
可达性矩阵无法正确计算,调试后发现是算法中未正确定义循环变量
七、程序设计总结
1.掌握了与离散数学理论相关的编程实现思想和方法,掌握了欧拉图和半欧拉图的判定。
2.利用邻接矩阵表示存在的边,通过Warshall算法求出无向图的可达性矩阵,如果是连通的话,那么可达性矩阵中每一个元素都应该为1,否则存在元素为0。
3.多次利用动态二维数组,并养成了在程序结束时释放动态二维数组内存的习惯。
4.明白了欧拉回路属于欧拉路的一种特殊情况,之前一直没有搞清这两者之间的关系。
在判断是欧拉图还是半欧拉图时,首先判断是不是连通图,然后判断是否只存在零个或者两个奇数度结点,有两个则是半欧拉图,零个则是欧拉图。
5.输出欧拉路时,利用递归深度搜索逆序输出结点,确保找到一条完整的路径,避免存在回路没有被遍历到。
评分细则
评分项
优秀
良好
中等
差
遵守机房规章制度
上机时的表现
学习态度
算法思想准备情况
程序设计能力
解决问题能力
课题功能实现情况
算法设计合理性
算法效能评价
报告书写认真程度
内容详实程度
文字表达熟练程度
回答问题准确度
简短评语
教师签名:
年月日
评分等级
备注
评分等级有五种:
优秀、良好、中等、及格、不及格