离散数学实验:随机生成图判断是否为欧拉图并给出欧拉(回)路

#include  
#include  
#include  
#include  
#include  
#define MAX 1000  
using namespace std;

int a[MAX][MAX];        //图的矩阵  
int b[MAX];     //记录各节点的度  
bool visit[MAX], ff = true;    //记录是否被访问过  
int euler[MAX], ans[MAX];     //欧拉路  
int m, n;    //  m表示结点个数,n表示边的条数  
int c[MAX][MAX];    //判断该边是否已经走过  
void randcreat();   //随机生成图,计算各结点的度,并输出矩阵  
void DFS(int x); //深度优先搜索判断是否为连通图  
bool judge_connect();       //判断是否联通  
void judge_euler();     //判断是否是欧拉(回)路  
void find_euler(int x, int y);     //以x为起点开始找是否存在欧拉(回)路  

void clearmap()//初始化
{
	ff = true;
	memset(b, 0, MAX*sizeof(int));
	memset(euler, -1, MAX*sizeof(int));
	memset(c, 0, MAX*sizeof(int));
	for (int i = 0; i < m; i++)
	{
		visit[i] = false;
		for (int j = 0; j < m; j++)
		{
			a[i][j] = 0;
			c[i][j] = 0;
		}
	}
}
int main()
{
	memset(euler, -1, MAX*sizeof(int));
	while (1)
	{
		cout << "请按顺序输入节点的个数和边的个数" << endl;
		cin >> m >> n;
		while(n>(m*(m - 1) / 2))
		{
			cout << "输入边数过大,请重新输入:" << endl;
			cin >> m >> n;
			
		}
		randcreat();
		if (judge_connect())
			cout << "随机生成的图是一个连通图!" << endl;
		else
		{
			cout << "该随机生成的图不是连通图" << endl;
			clearmap();
			continue;
		}
		cout << "其中每个节点的个数为\n";
		for (int i = 0; i2)
		cout << "这是非欧拉图或半欧拉图!" << endl;
	else
	{
		euler[0] = first;         //euler[]记录结点  
		find_euler(first, 1);
		if (num == 0)
			cout << "这是欧拉图" << endl;
		else
			cout << "这是半欧拉图" << endl;
		cout << "其中一条路径为:" << endl;
		for (int k = 0; k <= n; k++)
		{
			cout << setw(3) << ans[k]+1;
		}
		cout << endl << endl;
	}
}
void find_euler(int x, int y)
{
	if (euler[n] != -1)
	{
		if (ff)
		{
			for (int k = 0; k <= n; k++)
				ans[k] = euler[k];
			ff = false;
		}
		return;
	}
	for (int i = 0; i

你可能感兴趣的