fleury算法求欧拉回路

fleury算法求欧拉回路

方法一
是从这个的基础上写的，我就把输入矩阵换成了输入边
添加链接描述

#include
#include 
using namespace std;
//该算法适用于无向欧拉图找出具体的欧拉通路 
int main()
{
	int n,m,s,e;
	cout << "please input: " << endl;
	cin >> n >> m;

	vector> k(n + 1, vector(n + 1, 0));
	vector a(n + 1);

	for (int i = 0; i < m; i++){
		cin >> s >> e;
		k[s][e] = ++k[e][s];
	}
	int start,present = 1, tmp = 0;
	int num = 0;
	for (int i = 1; i <= n; i++) {
		int tt = 0;
		for (int j = 1; j <= n; j++) {
			if (k[i][j] == 1)
				tt++;
		}
		if (tt % 2 == 1) {
			num++;
			present = i;
		}
	}
	start = present;

	for (int i = 1; i <= n; i++) {
		int col = 0;
		for (int kk = 1; kk <= n; kk++) {
			col += k[kk][i];
		}
		a[i] = col;	//ru du
	}

	if (num != 0) {
		cout << "dont have euler loop" << endl;
		return 0;
	}
	cout << present << endl;
	system("pause");
	
	//算法思想：能不走桥就不走桥 
	while (true)
	{
		int flag2 = 0, flag1 = 0;

		for (int j = 1; j <= n; j++)//遍历该点与其它所有点的邻接关系 
		{
			if (present == j || k[present][j] == 0)
				continue;
			if (a[j] >= 2)//找到第一条非桥，就走它 
			{
				flag2++;//记录是否存在非桥 
				a[j]--;//边是二元关系，两个点都要改变；包括了环的情况 
				a[present]--;
				cout << "(" << present << "," << j << ")" << " ";//模拟走的道路 
				k[present][j]--;
				k[j][present]--;
				present = j;//更新当前点 
				break;//找到就进入下一个点 
			}
			if (a[j] == 1 && flag1 == 0)//记录第一个与当前点存在一条边（不一定是割边）的点 
			{
				flag1++;
				tmp = j;
			}
		}

		if (flag2 == 0 && flag1 == 1)//只能走桥 
		{
			a[present]--;
			a[tmp]--;
			k[present][tmp]--;
			k[tmp][present]--;
			cout << "(" << present << "," << tmp << ")" << " ";
			present = tmp;

		}
		if (flag2 == 0 && flag1 == 0)break;//当矩阵为零矩阵时结束 
	}
	return 0;

}

方法二dfs

#include
#include 
#include 
using namespace std;

const int maxn = 105;

int n, m;
bool edge[maxn][maxn];
int start;//起点 
int num;//奇度顶点的个数 
int degree[maxn];//顶点的度 
stack st;

void input() {
	int u, v;
	scanf_s("%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		scanf_s("%d%d", &u, &v);
		edge[u][v] = edge[v][u] = 1;
		degree[u]++; degree[v]++;
	}

	num = 0; start = 1;
	for (int i = 1; i <= n; i++) {
		if (degree[i] & 1) {
			start = i; num++;
		}
	}

}

void dfs(int s) {
	st.push(s);
	for (int i = 1; i <= n; i++) {
		if (edge[s][i] > 0) {
			edge[s][i] = edge[i][s] = 0;
			dfs(i);
			break;
		}
	}
}

void fleury(int s) {
	bool flag;
	st.push(s);
	while (!st.empty()) {
		flag = 0;
		for (int i = 1; i <= n; i++) {
			if (edge[st.top()][i] > 0) {
				flag = 1; break;
			}
		}
		if (flag) {
			int x = st.top();
			st.pop();
			dfs(x);
		}
		else {
			//要走的边是个桥
			stack temp = st;
			while (!temp.empty()) {
				printf("%d", temp.top());
				temp.pop();
			}
			cout << endl;
			printf("%dn", st.top());
			st.pop();
		}
	}
}

void solve() {
	if (num == 0 || num == 2) fleury(2);
	else puts("No Euler path");
}

int main() {
	input();
	solve();
	return 0;
}