南邮|离散数学实验四（图的生成及欧拉(回)路的确定）-Toy模板网

这篇具有很好参考价值的文章主要介绍了南邮|离散数学实验四（图的生成及欧拉(回)路的确定）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

内容：随机生成含指定节点数量n的无向连通图，并确定其中有无欧拉(回)路，若有则需要获取至少一条路径并输出。

要求：能随机生成无向连通图并正确判断其是否为(半)欧拉图，若是欧拉图，则还需输出至少一条欧拉(回)路。

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <string>
#include <cstring>
using namespace std;

int N;		//随机数N
int **M;	//关联矩阵
int LTFlag; //连通标志
int OLLFlag;//欧拉路标志
int OLHLFlag;//欧拉回路标志

//正整数转字符串 
string IntegerToString(int integer) {
	if(integer==0) return "0";
	int count=0;
	int temp=integer;
	while(temp) {
		count++;
		temp/=10;
	}
	string s = "";
	temp=integer;
	for(int i=0; i<count; i++) {
		s=s+(char)(temp%10+'0');
		temp/=10;
	}
	reverse(s.begin(),s.end());
	return s;
}

//输出关联矩阵
void ToString() {
	for(int i=0; i<N; i++) {
		for(int j=0; j<N; j++) {
			cout << M[i][j] << " ";
		}
		cout << endl;
	}
}

//生成随机矩阵
void RandM() {
	srand((unsigned)time(NULL));
	for(int i=0; i<N; i++) {
		for(int j=i; j<N; j++) {
			if(i==j) {
				M[i][j]=0;
				continue;
			}
			int k = rand()%100;
			if(k>50) {
				M[i][j]=1;
				M[j][i]=1;
			} else {
				M[i][j]=0;
				M[j][i]=0;
			}
		}
	}
}

//判断是否连通 (War Shall)
void  LianTong() {
	int temp[N][N];
	for(int i=0; i<N; i++) {
		for(int j=0; j<N; j++) {
			temp[i][j]=M[i][j];
		}
	}
	for(int i=0; i<N; i++) {
		for(int j=0; j<N; j++) {
			if(temp[j][i]==1) {
				for(int k=0; k<N; k++) {
					temp[j][k]=temp[j][k] || temp[i][k];
				}
			}
		}
	}
	for(int i=0; i<N; i++) {
		for(int j=0; j<N; j++) {
			if(temp[i][j]==0) return;
		}
	}
	LTFlag=1;
}

//判断欧拉路
void OuLaLu() {
	int count=0;
	for(int i=0; i<N; i++) {
		int du=0;
		for(int j=0; j<N; j++) {
			if(M[i][j]==1) {
				du++;
			}
			if(M[i][j]==1&&i==j) {
				du++;
			}
		}
		if(du%2!=0) {
			count++;
		}
	}
	if(count==0 || count ==2) {
		OLLFlag=1;
	}
}

//判断欧拉回路
void OuLaHuiLu() {
	int count=0;
	for(int i=0; i<N; i++) {
		int du=0;
		for(int j=0; j<N; j++) {
			if(M[i][j]==1) {
				du++;
			}
			if(M[i][j]==1&&i==j) {
				du++;
			}
		}
		if(du%2==1) {
			return;
		}
	}
	OLHLFlag=1;
}

//输出欧拉路
void PrintOuLaLu(int k,int **v,int start,string s) {
	int flag=1;
	for(int i=0; i<N; i++) {
		for(int j=0; j<N; j++) {
			if(v[i][j]==1) {
				flag=0;
				break;
			}
		}
		if(!flag) {
			break;
		}
	}
	if(flag) {
		cout << s << endl;
		return ;
	}
	for(int i=0; i<N; i++) {
		if(M[k][i]==1&&v[k][i]==1) {
			v[k][i]=v[i][k]=0;
			string temp=s;
			s=s+"->";
			s=s+(char)(i+'0');
			PrintOuLaLu(i,v,start,s);
			v[k][i]=v[i][k]=1;
			s=temp;
		}
	}
}

//输出欧拉回路
void PrintOuLaHuiLu(int k,int **v,int start,string s) {
	int flag=1;
	for(int i=0; i<N; i++) {
		for(int j=0; j<N; j++) {
			if(v[i][j]==1) {
				flag=0;
				break;
			}
		}
		if(!flag) {
			break;
		}
	}
	if(flag) {
		if(start==k) {
			cout << s << endl;
		}
		return ;
	}
	for(int i=0; i<N; i++) {
		if(M[k][i]==1&&v[k][i]==1) {
			v[k][i]=v[i][k]=0;
			string temp=s;
			s=s+"->";
			s=s+(char)(i+'0');
			PrintOuLaHuiLu(i,v,start,s);
			v[k][i]=v[i][k]=1;
			s=temp;
		}
	}
}

void Input() {
	cin >> N;
	M = new int *[N];
	for(int i=0; i<N; i++) {
		M[i] = new int[N];
	}
}

void Output() {
	do {
		RandM();
		LianTong();
	} while(!LTFlag);
	cout << "关联矩阵" << endl;
	ToString();
	OuLaLu();
	cout <<(OLLFlag?"是":"不是") <<"半欧拉图" << endl;
	if(OLLFlag) {
		int **v=M;
		for(int i=0; i<N; i++) {
			PrintOuLaLu(i,v,i,IntegerToString(i));
		}
	}
	OuLaHuiLu();
	cout <<(OLHLFlag?"是":"不是")<< "欧拉图" << endl;
	if(OLHLFlag)  {
		int **v=M;
		for(int i=0; i<N; i++) {
			PrintOuLaHuiLu(i,v,i,IntegerToString(i));
		}
	}
}
int main() {
	Input();
	Output();
	return 0;
}

南邮离散数学实验,离散数学,算法,图论,c++