图的随机生成及欧拉回路的确定.docx

图的随机生成及欧拉回路的确定.docx

《图的随机生成及欧拉回路的确定.docx》由会员分享，可在线阅读，更多相关《图的随机生成及欧拉回路的确定.docx（25页珍藏版）》请在冰点文库上搜索。

图的随机生成及欧拉回路的确定

实验报告

（/学年第一学期）

课程名称

离散数学

实验名称

图的随机生成及欧拉（回）路的确定

实验时间

年

月

日

指导单位

指导教师

学生姓名

班级学号

学院（系）

专业

实验报告

实验名称

图的随机生成及欧拉（回）路的确定

指导教师

实验类型

上机实验

实验学时

4

实验时间

一、实验目的和要求

目的：

编程随机生成n个结点的无向图或者有向图并能判定该无向图或者有向图是否存在欧拉（回）路，若是则给出欧拉（回）路。

要求：

对给定n个结点，随机生成邻接矩阵以确定某无向或者有向简单图并进行是否存在欧拉（回）路的判定，若符合则给出至少一条欧拉回路或欧拉路。

二、实验环境（实验设备）

硬件:

PC机。

软件:

Code:

:

Blocks（C++）

三、实验原理及内容

内容：

图的随机生成：

首先由用户选择是生成无向图还是有向图，再读入用户输入的结点个数，然后调用对应的无向图类或者有向图类的构造函数，在构造函数中随机生成邻接矩阵，计算可达性矩阵并且输出这两种矩阵。

欧拉（回）路的确定：

调用对应的无向图类或者有向图类中的判定是否存在欧拉路的函数和判定是否存在欧拉回路的函数，如果存在，输出欧拉（回）路存在，并且调用遍历欧拉路或者欧拉回路的函数。

原理：

建立一个图类（父类），在图类中用n储存结点个数，用**a指向一个二维数组存储邻接矩阵，用**p指向的二维数组储存可达性矩阵，建立图类的构造函数、析构函数、输出邻接矩阵的函数、输出可达性矩阵的函数、判断是否连通的函数。

由于两种图中的判断是否存在欧拉（回）路的原理不同，所以建立图类的两个派生类——无向图类和有向图类，在类中分别建立各自的判断是否存在欧拉（回）路的函数，以及遍历欧拉（回）路的函数。

这些函数的原理就是欧拉（回）路判定的充要条件，结合邻接矩阵和可达性矩阵的特点编写即可。

程序：

#include

#include

#include

#include

usingnamespacestd;

classgraph//图类

{

protected:

intn;//结点数

int**a;//储存邻接矩阵

int**p;//储存可达性矩阵

public:

graph（intsize）;

~graph（）;

voidPrint_linjie（）;//输出邻接矩阵

voidPrint_keda（）;//输出可达性矩阵

boolLiantong_or_not（）;//判断图是否连通

};

graph:

:

graph（intsize）

{

n=size;

srand（time（NULL））;

a=newint*[n];

for（inti=0;i

{

a[i]=newint[n];

for（intj=0;j

{

a[i][j]=a[j][i]=rand（）%2;

}

a[i][i]=0;

}

p=newint*[n];

for（inti=0;i

{

p[i]=newint[n];

for（intj=0;j

{

p[i][j]=0;

}

}

}

graph:

:

~graph（）

{

for（inti=0;i

{

delete[]a[i];

}

delete[]a;

for（inti=0;i

{

delete[]p[i];

}

delete[]p;

}

voidgraph:

:

Print_linjie（）

{

for（inti=0;i

{

for（intj=0;j

{

cout<

}

cout<

}

cout<

}

voidgraph:

:

Print_keda（）

{

for（inti=0;i

{

for（intj=0;j

{

cout<

}

cout<

}

cout<

}

boolgraph:

:

Liantong_or_not（）

{

for（inti=0;i

{

for（intj=0;j

{

if（i!

=j&&p[i][j]==0）

{

returnfalse;

}

}

}

returntrue;

}

classYgraph:

publicgraph//有向图类

{

public:

Ygraph（intsize）;

~Ygraph（）{}

boolOulalu_or_not（int&begin）;//判断有向图是否存在单向欧拉路

boolOulahuilu_or_not（）;//判断有向图是否存在单向欧拉回路

voidDFS（intbegin）;

private:

voidDFS（intbegin,intk,bool**visit）;

};

Ygraph:

:

Ygraph（intsize）:

graph（size）

{

srand（time（NULL））;

for（inti=0;in;i++）

{

for（intj=0;jn;j++）

{

this->a[i][j]=rand（）%2;

}

this->a[i][i]=0;

}

for（inti=0;in;i++）

{

for（intj=0;jn;j++）

{

if（this->a[i][j]==1）

{

for（intk=0;kn;k++）

{

if（this->a[i][k]||this->a[j][k]）

{

p[i][k]=1;

}

}

}

}

}

}

boolYgraph:

:

Oulahuilu_or_not（）

{

if（!

Liantong_or_not（））

{

returnfalse;

}

for（inti=0;in;i++）

{

intcount1=0,count2=0;

for（intj=0;jn;j++）

{

if（this->a[i][j]）

{

count1++;

}

if（this->a[j][i]）

{

count2++;

}

}

if（count1!

=count2）

{

returnfalse;

}

}

returntrue;

}

boolYgraph:

:

Oulalu_or_not（int&begin）

{

if（!

Liantong_or_not（））

{

returnfalse;

}

intcount=0;

int*r=newint[this->n];//储存入度与初度不同的结点的出度

int*s=newint[this->n];//储存入度与初度不同的结点的入度

for（inti=0;in;i++）

{

intcount1=0,count2=0;

for（intj=0;jn;j++）

{

if（this->a[i][j]）

{

count1++;

}

if（this->a[j][i]）

{

count2++;

}

}

if（count1!

=count2）

{

r[count]=count1;

s[count]=count2;

if（count1>count2）

{

begin=i;

}

count++;

}

}

if（count!

=2）

{

returnfalse;

}

else

{

if（r[0]-s[0]==1&&s[1]-r[1]==1||s[0]-r[0]==1&&r[1]-s[1]==1）

{

returntrue;

}

else

{

returnfalse;

}

}

}

voidYgraph:

:

DFS（intbegin）

{

bool**visit=newbool*[this->n];

for（inti=0;in;i++）

{

visit[i]=newbool[this->n];

for（intj=0;jn;j++）

{

if（a[i][j]）

{

visit[i][j]=true;

}

else

{

visit[i][j]=false;

}

}

}

cout<

for（intk=0;kn;k++）

{

DFS（begin,k,visit）;

}

cout<

delete[]visit;

}

voidYgraph:

:

DFS（intj,intk,bool**visit）

{

if（visit[j][k]）

{

visit[j][k]=false;

cout<

for（inti=0;in;i++）

{

if（i!

=k）

{

DFS（k,i,visit）;

}

}

}

}

classWgraph:

publicgraph//无向图类

{

public:

Wgraph（intsize）;

~Wgraph（）{}

boolOulalu_or_not（int&begin）;//判断是否存在欧拉路

boolOulahuilu_or_not（）;//判断是否存在欧拉回路

voidDFS（intbegin）;

private:

voidDFS（intbegin,intk,bool**visit）;

};

Wgraph:

:

Wgraph（intsize）:

graph（size）

{

srand（time（NULL））;

for（inti=0;in;i++）

{

for（intj=0;j

{

this->a[i][j]=this->a[j][i]=rand（）%2;

}

this->a[i][i]=0;

}

for（inti=0;in;i++）

{

for（intj=0;jn;j++）

{

if（this->a[i][j]==1）

{

for（intk=0;kn;k++）

{

if（this->a[i][k]||this->a[j][k]）

{

p[i][k]=1;

}

}

}

}

}

}

boolWgraph:

:

Oulalu_or_not（int&begin）

{

if（!

Liantong_or_not（））

{

returnfalse;

}

intcount=0;

for（inti=0;in;i++）

{

intnumber=0;

for（intj=0;jn;j++）

{

if（this->a[i][j]）

{

number++;

}

}

if（number%2）

{

count++;

begin=i;

}

}

if（count==0||count==2）

{

returntrue;

}

else

{

returnfalse;

}

}

boolWgraph:

:

Oulahuilu_or_not（）

{

if（!

Liantong_or_not（））

{

returnfalse;

}

for（inti=0;in;i++）

{

intnumber=0;

for（intj=0;jn;j++）

{

if（this->a[i][j]）

{

number++;

}

}

if（number%2）

{

returnfalse;

}

}

returntrue;

}

voidWgraph:

:

DFS（intbegin）

{

bool**visit=newbool*[this->n];

for（inti=0;in;i++）

{

visit[i]=newbool[this->n];

for（intj=0;jn;j++）

{

if（a[i][j]）

{

visit[i][j]=true;

}

else

{

visit[i][j]=false;

}

}

}

cout<

for（intk=0;kn;k++）

{

DFS（begin,k,visit）;

}

cout<

delete[]visit;

}

voidWgraph:

:

DFS（intj,intk,bool**visit）

{

if（visit[j][k]）

{

visit[j][k]=visit[k][j]=false;

cout<

for（inti=0;in;i++）

{

DFS（k,i,visit）;

}

}

}

intmain（）

{

intflag=1;

while（flag==1）

{

system（"cls"）;

intflag_2=0;

intsize,choose,begin=0;

cout<<"请选择要生成的图的类型（1、有向图2、无向图）：

";

cin>>choose;

cout<

";

cin>>size;

Ygraphg（size）;

Wgraphh（size）;

switch（choose）

{

case1:

cout<

"<

g.Print_linjie（）;

cout<<"该图的可达性矩阵为：

"<

g.Print_keda（）;

if（g.Oulalu_or_not（begin））

{

cout<<"该图存在欧拉路！

"<

cout<<"欧拉路为：

";

g.DFS（begin）;

}

else

{

cout<<"该图不存在欧拉路！

"<

}

if（g.Oulahuilu_or_not（））

{

cout<<"该图存在欧拉回路！

"<

cout<<"欧拉回路为：

";

g.DFS（begin）;

}

else

{

cout<<"该图不存在欧拉回路！

"<

}

break;

case2:

cout<

"<

h.Print_linjie（）;

cout<<"该图的可达性矩阵为：

"<

h.Print_keda（）;

if（h.Oulalu_or_not（begin））

{

cout<<"该图存在欧拉路！

"<

cout<<"欧拉路为：

";

h.DFS（begin）;

}

else

{

cout<<"该图不存在欧拉路！

"<

}

if（h.Oulahuilu_or_not（））

{

cout<<"该图存在欧拉回路！

"<

cout<<"欧拉回路为：

";

h.DFS（begin）;

}

else

{

cout<<"该图不存在欧拉回路！

"<

}

break;

default:

cout<

"<

}

cout<

（继续使用请输入1，否则输入0）：

";

cin>>flag;

}

return0;

}

流程图：

举例使用：

1、无向图不存在欧拉路和欧拉回路的例子

2、无向图存在欧拉路，但是不存在欧拉回路的例子

3、无向图存在欧拉路且为欧拉回路的例子

4、有向图不存在欧拉路和欧拉回路的例子

5、有向图存在欧拉路的例子

6、有向图存在欧拉回路的例子

四、实验小结（包括问题和解决方法、心得体会、意见与建议等）

这次实验是要做图的随机生成及欧拉（回）路的确定，由于没有明确的要求，我最开始决定做无向图的随机生成及只判断是否存在欧拉（回）路而不给出具体的欧拉（回）路，这样简单一点。

我运用了类的继承与派生的知识，先建立一个图类，再将无向图类建立为其派生类，类的成员函数只需根据定义及判定定理并结合两个矩阵的特点来建立即可，在生成可达性矩阵时，为了加快系统的运算，我通过查阅资料运用了Warshall算法的原理建立这个函数。

这些完成之后，我利用课后的时间将这个程序进一步完善，增加了有向图类及其成员函数，并且增加了对欧拉（回）路的遍历，在设计遍历的函数时，运用了函数递归的相关知识。

这次离散实验让我对C++的编程语言有了更强的运用能力，尤其是继承与派生的知识有了更深刻的理解，让我明白了在平时的学习中要勤查资料，多学习一些课外知识。

离散数学和编程知识、数据结构是息息相关、密不可分的。

以后我将更加认真学习离散数学，并且更多地将编程的知识运用起来，提升自己的实际运用能力。

五、指导教师评语

成绩

批阅人

日期