一般的版本
void euler(int u) { for (int v = 0; v < n; ++v) if (G[u][v] && !vis[u][v]) { vis[u][v] = vis[v][u] = 1; euler(v); path.push_back(v); } }递归版本(图很大，不能用邻接矩阵)
#include<iostream> #include<vector> using namespace std; const int maxn = 10005; const int maxm = ; struct Edge{ int M,vis;//M是u+v Edge(int a = 0,int c = 0) : M(a), vis(c) {}; }; vector<Edge> Edges; vector<int> G[maxn];//G[k]代表k结点相连的路径编号(Edges[]编号) vector<int> path; int n, m,a,b; void euler(int u) { for (int i=0;i<G[u].size();++i) if (!Edges[G[u][i]].vis) { int v = Edges[G[u][i]].M - u; Edges[G[u][i]].vis = 1; euler(v); path.push_back(v); } }迭代版本(栈溢出的情况下使用)
#include<iostream> #include<vector> using namespace std; const int maxn = 10005; const int maxm = ; struct Edge{ int M,vis; Edge(int a = 0,int c = 0) : M(a), vis(c) {}; }; vector<Edge> Edges; vector<int> G[maxn];//G[k]代表k结点相连的路径编号(Edges[]编号) vector<int> path; int n, m,a,b,i; Edge x; vector<Edge> sta;//代表：M=u,vis=i void euler(int u) { i = 0; while (1) { for (; i<G[u].size(); ++i) if (!Edges[G[u][i]].vis) { int v = Edges[G[u][i]].M - u; Edges[G[u][i]].vis = 1; sta.push_back(Edge(u, i)); u = v; i = 0; break; } if (!i) continue;//只有break下来的i是等于0的，其他都是>0,不存在不连通图的欧拉路径 if (sta.empty()) break; x = sta.back(); sta.pop_back(); u = x.M, i = x.vis; path.push_back(Edges[G[u][i++]].M - u); } }版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/233885.html原文链接：https://javaforall.net
