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

由天下分享时间：2024/9/11 3:07:16 加入收藏我要投稿点赞

《离散数学》实验报告

（2015 / 2016 学年第一学期）

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

专业信息安全学生姓名班级学号指导教师指导单位计算机学院计算机科学与技术系日期 2015年12月29日

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

一、实验内容和要求

内容：编程随机生成n个结点的无向图并能进行（半）欧拉图的判定，若是则给出欧拉（回）路。

要求：对给定n个结点，随机生成邻接矩阵以确定某无向简单图并进行欧拉图和半欧拉图的判定，若符合则给出至少一条欧拉回路或欧拉路。

二、实验目的

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

三、实验任务

1、输入结点个数据生成随机图 2、进行（半）欧拉图的判定 3、若是则给出欧拉（回）路。

四、实验内容

#include

#include using namespace std; class Euler {

public: Euler(int num); ~Euler();

void DFS(int begin); //公有的深度优先搜索函数 void inputEdge(); //输入边 void PrintAM(); //打印邻接矩阵 void PrintRM(); //打印可达性矩阵 void Warshall(); //Warshall算法求可达性矩阵 bool IsConnected(); / /判断图是否连通 int IsEorSE(); //判断图是欧拉图还是半欧拉图 bool isEuler; private:

void DFS(int u,int v,bool **visited); / /私有的深度优先搜索函数 int n;

int **a; //定义动态二维数组 int **p; //定义可达性矩阵

int *b; //存储每个结点的度数 };

Euler::Euler(int num) //构造函数 { isEuler=false; n=num; int i,j; a=new int*[n]; for(i=0;i

Euler::~Euler()//析构函数 { int i; for(i=0;i

void Euler::inputEdge() { srand((unsigned)time(NULL)); for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { a[i][j] = 0+rand()%2; a[j][i]=a[i][j];

}

//随机生成无向图 } for(int ii=0;ii

void Euler::PrintAM() { cout<<\随机生成的图为：\ for(int i=0;i

void Euler::Warshall() { for(int i=0;i0) p[j][k]=1; } } }

void Euler::PrintRM() { cout<<\可达性矩阵：\ for(int i=0;i

}

bool Euler::IsConnected() { int i,j;

bool flag=true; / /flag标记是否连通 for(i=0;i

if(!flag) cout<<\该图不是连通的\else { for(i=0;i

if(a[i][j]==1&&i!=j) //由边计算结点的度数 { b[i]++;b[j]++; } } } return flag; }

int Euler::IsEorSE() { int i,count=0,begin=-1; cout<<\每个结点的度数：\ for(i=0;i

for(i=0;i