求欧拉回路的Fleury算法

欧拉路径貌似很多博客都喜欢⽤⼀笔画来引⼊欧拉路径，但像您这样的强者时⽆需那些繁琐的东西，我们直接进⼊正题。

定义：图中经过所有边恰好⼀次的路径叫做欧拉路径。

如果起点和终点⼀样，那它就是欧拉回路。

判定：判定当前图中是否存在欧拉路径其实⽐寻找更⿇烦显然，欧拉回路也是欧拉路径，但为了⽅便区分，下⽂判定中的欧拉路径特指起点和终点不同。

判定⽅法：⾸先，当且仅当这张图将有向边视为⽆向边时联通。

1. 有向图欧拉路径：图中恰好存在⼀个点（起点）出度⽐⼊度多1，恰好⼀个点（终点）⼊度⽐出度多1，剩下所有点⼊度等于出度。

2. 有向图欧拉回路：图中所有点⼊度等于出度（任⼀点都可以做起点和终点）。

3. ⽆向图欧拉路径：图中恰好有两个点的度数为奇数（起点和终点），其他所有点的度数为偶数。

4. ⽆向图欧拉回路：图中所有点的度数都为偶数（任⼀点都可以做起点和终点）。

寻找：算法⼀：Fluery 算法。

时间复杂度O(m2)，不常⽤。

算法⼆：Hierholzer 算法。

时间复杂度O(m)，常⽤。

只写 Hierholzer 算法，做法⾮常简单。

1. 从起点开始dfs，标记选了的边不能重复选，这⾥⽤类似Dinic的当前弧优化。

2. 当前点不存在出边时回退，并将当前点⼊栈P。

3. 当dfs结束时倒序输出栈P中的节点即可。

算法导论上似乎有该算法证明。

例题：题⽬保证联通，所以直接判断⼊度和出度即可。

要求字典序最⼩，那么每次都要选能到达的最⼩的点。

可以将边离线下来按v从⼤到⼩排序，然后依次插⼊到链式前向星⾥，这样可以保证每次选到的都是最⼩的。

当前弧优化不加复杂度就假了。

code:#include<bits/stdc++.h>using namespace std;#define int long long#define in read()inline int read(){int p=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}return p*f;}const int N=1e5+5;const int M=2e5+5;int n,m;struct edge{int v,nxt;}e[M];inline void insert(int u,int v){e[++en].v=v;e[en].nxt=head[u];head[u]=en;}struct QWQ{int u,v;}E[M];inline bool cmp(QWQ a,QWQ b){return a.v>b.v;}int p[M],pn;void dfs(int u){for(int i=head[u];i;i=head[u]){int v=e[i].v;head[u]=e[i].nxt;dfs(v);}p[++pn]=u;}int flagin,flagout,flag;int ind[N],outd[N];int S=1;signed main(){n=in,m=in;for(int i=1;i<=m;i++)E[i].u=in,E[i].v=in,outd[E[i].u]++,ind[E[i].v]++;sort(E+1,E+1+m,cmp);for(int i=1;i<=m;i++)insert(E[i].u,E[i].v);for(int i=1;i<=n;i++){if(ind[i]!=outd[i])flag++;if(ind[i]==outd[i]+1)flagout++;if(ind[i]+1==outd[i])flagin++,S=i;}if(flag==0||(flag==2&&flagout==1&&flagin==1)){dfs(S);for(int i=pn;i>=1;i--)cout<<p[i]<<' ';}else cout<<"No";return 0;}练习：将每个字母视为点，单词视为边，就和上⾯差不多了，注意欧拉路径的起始点。

电⼦科技⼤学《图论及其应⽤》复习总结--第四章欧拉图与哈密尔顿图第四章欧拉图与哈密尔顿图(⼀)、欧拉图及其性质(1)、问题背景---欧拉与哥尼斯堡七桥问题问题：对于图G，它在什么条件下满⾜从某点出发，经过每条边⼀次且仅⼀次，可以回到出发点？注：⼀笔画----中国古⽼的民间游戏（存在欧拉迹）要求：对于⼀个图G, 笔不离纸, ⼀笔画成.拓展：三笔画：在原图上添加三笔，可使其变为欧拉图。

定义1 对于连通图G，如果G中存在经过每条边的闭迹，则称G为欧拉图，简称G为E图。

欧拉闭迹⼜称为欧拉环游，或欧拉回路。

定理1 下列陈述对于⾮平凡连通图G是等价的：(1) G是欧拉图；(2) G的顶点度数为偶数；(3) G的边集合能划分为圈。

推论1 连通图G是欧拉图当且仅当G的顶点度数为偶。

推论2 连通⾮欧拉图G存在欧拉迹当且仅当G中只有两个顶点度数为奇数。

证明：若G和H是欧拉图，则G×H是欧拉图。

若G是⾮平凡的欧拉图，则G的每个块也是欧拉图。

(⼆)、Fleury算法(欧拉图中求出⼀条具体欧拉环游的⽅法)⽅法是尽可能避割边⾏⾛(三)、中国邮路问题（最优欧拉环游，管梅⾕）定理2 若W是包含图G的每条边⾄少⼀次的闭途径，则W具有最⼩权值当且仅当下列两个条件被满⾜：(1) G的每条边在W中最多重复⼀次；(2) 对于G的每个圈上的边来说，在W中重复的边的总权值不超过该圈⾮重复边总权值。

(四)、哈密尔顿图的概念定义1 ：如果经过图G的每个顶点恰好⼀次后能够回到出发点，称这样的图为哈密尔顿图，简称H图。

所经过的闭途径是G的⼀个⽣成圈，称为G的哈密尔顿圈。

定义2: 如果存在经过G的每个顶点恰好⼀次的路，称该路为G的哈密尔顿路，简称H路。

(五)、哈密尔顿图性质与判定1、性质定理【必要条件】；定理1 (必要条件) 若G为H图，则对V(G)的任⼀⾮空顶点⼦集S，有：w(G−S)≤|S|注：不等式为G是H图的必要条件，即不等式不满⾜时，可断定对应图是⾮H、图。

欧拉路径(欧拉回路)算法欧拉路径（欧拉回路）相关定义：若图G中存在这样一条路径，使得它恰通过G中每条边一次,则称该路径为欧拉路径。

若该路径是一个圈，则称为欧拉回路。

具有欧拉回路的图称为欧拉图（简称E图）。

具有欧拉路径但不具有欧拉回路的图称为半欧拉图。

判断图是否为欧拉图：无向图为欧拉图，当且仅当为连通图且所有顶点的度为偶数。

无向图为半欧拉图，当且仅当为连通图且除了两个顶点的度为奇数之外，其它所有顶点的度为偶数。

有向图为欧拉图，当且仅当其基图（忽略有向图所有边的方向，得到的无向图称为该有向图的基图）连通，且所有顶点的入度等于出度。

有向图为半欧拉图，当且仅当其基图连通，且有且仅有一个顶点的入度比出度大1、有且仅有一个顶点的入度比出度小1，其它所有顶点的入度等于出度。

欧拉回路（路径）的算法：有向图：第一步，判断是否存在欧拉路径（欧拉回路），如果不存在，算法结束。

第二步，如果存在欧拉路径，从入度比出度小1的点开始BFS；如果存在欧拉回路，从任意一点开始。

第三步，设DFS到点u，遍历u的出边e(u,v)。

第四步，如果e未被标记，转到第五步，否则转到第三步。

第五步，标记e(u,v)，DFS点v。

第六步，边e(u,v)入栈。

第七步，完成DFS后，从栈顶顺序输出边构成一个欧拉路径（欧拉回路）。

无向图：第一步，判断是否存在欧拉路径（欧拉回路），如果不存在，算法结束。

第二步，如果存在欧拉路径，从度为奇数的点开始BFS；如果存在欧拉回路，从任意一点开始。

第三步，设DFS到点u，遍历u的出边e(u,v)。

第四步，如果e未被标记，转到第五步，否则转到第三步。

第五步，标记e(u,v)及它的反向边，DFS点v。

第六步，边e(u,v)入栈。

第七步，完成DFS后，从栈顶顺序输出边构成一个欧拉路径（欧拉回路）。

离散数学中初级回路和简单回路离散数学是一门研究离散量和离散结构的学科，在其中初级回路和简单回路是常见概念之一。

本文将介绍初级回路和简单回路的概念、性质及应用。

一、初级回路和简单回路的概念1.初级回路初级回路又称为欧拉回路，是指经过图中每个边恰好一次的回路。

当图G中存在欧拉回路，G被称为欧拉图。

欧拉回路必须是连通图，而且每个顶点的度数都是偶数。

同样地，对于 n 个顶点的简单连通图 G，G 是欧拉图当且仅当它的每个顶点的度数都是偶数。

2.简单回路简单回路又称为哈密顿回路，是指经过图中每个顶点恰好一次的回路。

当图G中存在简单回路，G被称为哈密顿图。

在实际应用中，初级回路和简单回路有着不同的价值，前者被广泛应用于城市规划、通信网络等领域，而后者则被用于模拟电路、运输路线等问题的求解。

二、初级回路和简单回路的性质1.初级回路的性质对于 n 个顶点的欧拉图 G，设k 是一个连通分量，则 G 是欧拉图当且仅当 G 的每个连通分量都是欧拉图。

2.简单回路的性质对于 n 个顶点的简单连通图 G，如果 v 是 G 的一点，则 G 是哈密顿图当且仅当 G-v 是哈密顿图。

3.初级回路和简单回路的关系对于 n 个顶点的连通图 G，如果 G 是欧拉图，那么 G 必须是哈密顿图。

但反过来并不成立，即哈密顿图不一定是欧拉图。

三、初级回路和简单回路的应用1.初级回路的应用欧拉回路被广泛应用于城市规划、通信网络等领域。

以城市规划为例，欧拉回路可以用来规划城市的交通系统，以实现绿色出行，节约能源，减少碳排放等目的。

同时，欧拉回路还可以用来测试网络中的通信障碍，以及计算机网络中的最短路径等问题。

2.简单回路的应用哈密顿回路被广泛应用于模拟电路、物流运输等领域。

以模拟电路为例，哈密顿回路可以用来分析电路中的开闭电路问题，以实现电路的优化设计和性能最大化。

同时，哈密顿回路还可以用来计算物流运输中的最短路径问题，以实现物流效率的提升。

总之，初级回路和简单回路是离散数学中的常见概念，具有重要的理论和实际应用价值。

一、欧拉回路所谓欧拉回路与哥尼斯堡7桥问题相联系的．在哥尼斯堡7桥问题中，欧拉证明了不存在这样的回路，使它经过图中每条边且只经过一次又回到起始点．与此相反，设G （V ，E ）为一个图，若存在一条回路，使它经过图中每条边且只经过一次又回到起始点，就称这种回路为欧拉回路，并称图G 为欧拉图．在一个图中，连接一个节点的边数称为该节点的度数．对欧拉图，我们有下列结果： 定理1 对连通图G （V ，E ），下列条件是相互等价的： （1）G 是一个欧拉图；（2）G 的每一个节点的度数都是偶数；（3）G 的边集合E 可以分解为若干个回路的并．证明 ：()()12⇒ 已知G 为欧拉图，则必存在一个欧拉回路．回路中的节点都是偶度数．()()23⇒ 设G 中每一个节点的度数均为偶数．若能找到一个回路C 1使G=C 1，则结论成立．否则，令G 1=G\C 1，由C 1上每个节点的度数均为偶数，则G 1中的每个节点的度数亦均为偶数．于是在G 1必存在另一个回路C 2．令G 2=G 1\C 2，···．由于G 为有限图，上述过程经过有限步，最后必得一个回路C r 使 G r =G r-1\C r 上各节点的度数均为零，即C r =G r-1．这样就得到Ｇ的一个分解 G C C C r =⋅⋅⋅12 ．()()31⇒ 设G C C C r =⋅⋅⋅12 ，其中i C （I=1,2,…,r ）均为回路．由于G 为连通图，对任意回路i C ,必存在另一个回路j C 与之相连，即i C 与j C 存在共同的节点．现在我们从图G 的任意节点出发，沿着所在的回路走，每走到一个共同的节点处，就转向另一个回路，···，这样一直走下去就可走遍G 的每条边且只走过一次,最后回到原出发节点，即G 为一个欧拉图．利用定理1去判断一个连通图是否为欧拉图比较容易，但要找出欧拉回路，当连通图比较复杂时就不太容易了．下面介绍一种求欧拉回路的算法．二、弗罗莱算法算法步骤如下：（1）任取起始点v v R 00,;→（2）设路)},({,),,({),,({1211201rr i i r i i i v v e v v e v v e R -⋅⋅⋅=已选出，则从E\},,,{21r e e e ⋅⋅⋅中选出边1+r e ，使1+r e 与ri v 相连，除非没有其它选择，G e r r \{}+1仍应为连通的．（3）重复步骤（2），直至不能进行下去为止．定理2 连通的有向图存在欧拉回路的充分必要条件是对任意节点，进入该节点边数（进数）与离开该点的边数（出数）相等．三、中国邮递员问题一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局．如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程．这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在1962年首次提出的，因此在国际上称之为中国邮递员问题．用图论的述语，在一个连通的赋权图G （V ，E ）中，要寻找一条回路，使该回路包含G 中的每条边至少一次，且该回路的权数最小．也就是说要从包含G 的每条边的回路中找一条权数最小的回路．如果G 是欧拉图，则很容易由弗罗莱算法求出一个欧拉回路，但是若G 不是欧拉图，即存在奇度数的节点，则中国由递员问题的解决要困难得多．本节的主要目标是给出在有奇度数节点的连通图中寻找最小权数的回路的方法．首先注意到，若图G 有奇数度节点，则G 的奇数度节点必是偶数个．把奇数度节点分为若干对，每对节点之间在G 中有相应的最短路，将这些最短路画在一起构成一个附加的边子集E '．令G / =G+E /，即把附加边子集E / 叠加在原图G 上形成一个多重图G /，这时G /中连接两个节点之间的边不止一条．显然G /是一个欧拉图，因而可以求出G /的欧拉回路．该欧拉回路不仅通过原图G 中每条边，同时还通过E / 中的每条边，且均仅一次．邮递员问题的难点在于当G 的奇数度节点较多时，可能有很多种配对方法，应怎样选择配对，能使相应的附加边子集E / 的权数ω(E / )为最小？为此有下列定理．定理 3 设G （V ，E ）为一个连通的赋权图，则使附加边子集E / 的权数ω(E / )为最小的充分必要条件是G+E / 中任意边至多重复一次，且G+E / 中的任意回路中重复边的权数之和不大于该回路总权数的一半．证明： 必要性．用反证法．设存在一种奇节点集的配对，使其附加边子集E / 权数 ω(E / )为最小．若 G+E / 中有一条边重复n n ()≥2次，由于G+E /为欧拉图，所以删去相应的二次重复边后仍为欧拉图．这样，相应的附加边子集的权数将减小，这与 ω(E /)为最小的假设矛盾．这说明E /中的边均互不相同．其次，若G+E / 中存在一个回路，使它的重复边的权数之和大于该回路总权数的一半，则在E / 中删去这些重复边（注意：这些边均在E /中），而代之以该回路的其余部分的边再重复一次．经过这种替代后所得到的边子集E //仍为附加子集，且ω(E //)<ω(E /)，又产生矛盾． 充分性．设有两个附加边子集E /和E //，均使G+E /和G+E //中每条边至多重复一次，且每个回路中的重复边的权数和不大该回路权数的一半，我们来证明ω(E /)=ω(E //)．首先注意到，由E /和E //不相同的部分组成的图（记为]\[//////）（E E EE G ）是由一个或若干个欧拉子图所组成的．这是因为E /＋E //中每个节点的度数均为偶数，而E /和E //的公共边数也是偶数，故]\[//////）（E E EE G 中每个节点的度数仍为偶数，所以它若为连通图时是一个欧拉图；若为非连通图时则由若干个欧拉子图组成．]\[//////）（E E EE G 的任何回路都由E /和E //中的边组成，而E /和E //在回路中的权数分别不大于该回路权数的一半，因而任何回路中属于E /中的权数之和与属于E //中的边数之和必定相等，所以ω(E /)=ω(E //)．它就是最优附加边子集的权数，即E /和E //均为使附加边子集的权数达到最小的最优附加边子集．由定理3可得一个寻找邮递员问题最优解的方法．现举例如下：例1 已知邮递员要投递的街道如图11-20所示，试求最优邮路．解 先找出奇节点：A 1，A 2，A 3，A 4，B 1，B 2，B 3，B 4．奇节点进行配对，不妨把A 1与B 1，A 2与B 2，A 3与B 3，A 4与B 4配对，求其最短路．显然它不是最优解．下面我们根据定理3来进行调解．第一次调整：删去多于一条的重复边，即A 3与B 3，A 4与B 4中的（A 4，B 3）．调整后，实际上成为A 1与B 1，A 2与B 2，A 3与A 4，B 3与B 4的配对，它们的最短路如图11-21所示． 第二次调整：发现在回路{A 1，A 2，B 2，A 4，B 3，B 4，B 1，A 1}中重复边的权数和为11，大于该回路权数20的一半．因而调整时，把该回路的重复边删去，代之以重复其余部分，得图11-22．可以看出，实际上是调整为A 1与A 2，B 1与B 4，A 3与A 4，B 2与B 3配对．第三次调整：在图11-22中发现回路{ A 3，A 4，B 2，A 3}中重复边的权数和为7，大于该回路权数10的一半，因而删去原重复边（A 3，V 2，A 4）和（A 4，B 2），而添加（B 2，A 3），得到图11-23．进行检查发现，既没有多于一条的重复边，也没有任何回路使其重复边的权数之和大于该回路的一半，因此图11-23就是最优的附加边子集E /，而G+E /为欧拉图，可由弗罗莱算法找出最优邮路．在现实生活中，很多问题都可以转化为中国邮递员问题，例如道路清扫时如何使开空车的总时间最少的问题等等．上面例1题所用的求最优邮路的方法叫“奇偶点图上作业法”．因为此方法要验证每个回路，很不方便，Edmods 和Johnson 在1973年提出一种比较有效的方法，有兴趣的读者可参考有关资料．习 题 11-31．证明，若图G 为欧拉图，则G 的边数不少于节点数．2．一名邮递员的投邮区，如下图11-24所示，每条边（街道）都有邮件需投递，各边旁所注的数字为该街道的长度，试求该邮区的最短投递路径及其长度． 3．求下列图11-25（a ）(b)所示的投邮区的最佳邮路及其长度．【算法】欧拉图，欧拉回路，Eular Circuit ，随机生成欧拉图，搜索欧拉回路背景：图论起源于18世纪，1736年瑞士数学家欧拉（Eular ）发表了图论的第一篇论文“哥尼斯堡七桥问题”。

龙源期刊网
Euler图中的中国邮路问题的Fleury算法
作者：刘勇
来源：《商情》2012年第26期
【摘要】本文首先对什么是中国邮路问题以及它的图论模型进行了解释，并对只含有偶顶点的Euler图中的中国邮路问题用Fleury算法做了解答，而这一方法在解决含有奇顶点的一般性的中国邮路问题，同样具有重要的参考价值。

【关键词】Euler图，中国邮路问题，Fleury算法（3）顶V的次数记成d(v)。

若从顶引出的该图形的弧的条数为奇数，则称这个顶为奇顶点，顶的次数为奇次；若为偶数，则顶为偶顶点，顶的次数为偶次。

中国邮路问题及其图论模型
中国邮路问题也称中国邮递员问题，是我国数学家管梅谷于1960年首次提出来的，这个问题的实际模型是：一位邮递员从邮局选好邮件去投递，然后返回邮局，他必须经过由他负责投递的每条街道至少一次，为这位邮递员设计一条投递线路，使其耗时最少。

我们上述的问题用图图形的语言表示出来，就有中国邮路问题的图论模型： Euler图中的中国邮路问题
4.1 Euler图的相关概念
定义1 :图中含有每一条边的行迹叫做Euler行迹；闭的Euler行迹叫做Euler回路；含有Euler回路的图叫做Euler图。

直观地讲，欧拉图就是从一个顶点出发每条边恰好通过一次又能回到出发顶点的那种图，即不重复的行遍所有的边再回到出发点。

下面给出Euler图的特征性描述：
4.2Fleury算法求解Euler回路中的中国邮路问题。

欧拉回路基本概念+判断+求解1.定义如果图G（有向图或者⽆向图）中所有边⼀次仅且⼀次⾏遍所有顶点的通路称作欧拉通路。

如果图G中所有边⼀次仅且⼀次⾏遍所有顶点的回路称作欧拉回路。

具有欧拉回路的图称为欧拉图（简称E图）。

具有欧拉通路但不具有欧拉回路的图称为半欧拉图。

2. 定理及推论欧拉通路和欧拉回路的判定是很简单的，请看下⾯的定理及推论。

⽆向图G存在欧拉通路的充要条件是：G为连通图，并且G仅有两个奇度结点（度数为奇数的顶点）或者⽆奇度结点。

推论1：1) 当G是仅有两个奇度结点的连通图时，G的欧拉通路必以此两个结点为端点。

2) 当G是⽆奇度结点的连通图时，G必有欧拉回路。

3) G为欧拉图（存在欧拉回路）的充分必要条件是G为⽆奇度结点的连通图。

有向图D存在欧拉通路的充要条件是：D为有向图，D的基图连通，并且所有顶点的出度与⼊度都相等；或者除两个顶点外，其余顶点的出度与⼊度都相等，⽽这两个顶点中⼀个顶点的出度与⼊度之差为1，另⼀个顶点的出度与⼊度之差为-1。

推论2：1) 当D除出、⼊度之差为1，-1的两个顶点之外，其余顶点的出度与⼊度都相等时，D的有向欧拉通路必以出、⼊度之差为1的顶点作为始点，以出、⼊度之差为-1的顶点作为终点。

2) 当D的所有顶点的出、⼊度都相等时，D中存在有向欧拉回路。

3) 有向图D为有向欧拉图的充分必要条件是D的基图为连通图，并且所有顶点的出、⼊度都相等。

3.欧拉通路回路存在的判断根据定理和推论，我们可以很好的找到欧拉通路回路的判断⽅法，定理和推论是来⾃离散数学的内容，这⾥就给出简明的判断⽅法：A.判断欧拉通路是否存在的⽅法有向图：图连通，有⼀个顶点出度⼤⼊度1，有⼀个顶点⼊度⼤出度1，其余都是出度=⼊度。

⽆向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。

B.判断欧拉回路是否存在的⽅法有向图：图连通，所有的顶点出度=⼊度。

⽆向图：图连通，所有顶点都是偶数度。

4.欧拉回路的应⽤A.哥尼斯堡七桥问题B.⼀笔画问题C.旋转⿎轮的设计5.欧拉回路的求解A. DFS搜索求解欧拉回路基本思路：利⽤欧拉定理判断出⼀个图存在欧拉回路或欧拉通路后，选择⼀个正确的起始顶点，⽤DFS算法遍历所有的边（每⼀条边只遍历⼀次），遇到⾛不通就回退。

欧拉回路的判断条件和构造方法我折腾了好久欧拉回路的判断条件和构造方法，总算找到点门道。

咱先说说这欧拉回路的判断条件。

最开始我完全是瞎摸索，我就拿着图在那看啊看。

后来才知道对于无向图来说，如果每个顶点的度数都是偶数，那这个图就存在欧拉回路。

就好比每个顶点都是有偶数条路能出去或者进来的，你要走一圈把每条路都走过还能回来，这就得每个顶点出去和进来的机会一样多，也就是度数为偶数啦。

我自己也画过一些图来验证，有一次我画了个简单的菱形图，每个顶点都连着两条边，度数是2，我就试着走，还真能在这个图里走出一个回路来。

可是我也犯过错，有个图我看着好像都连得挺好，但是有个顶点的度数是奇数，我当时没发现，还在那找回路，怎么找都不对，后来才发现这个问题，所以判断无向图的每个顶点度数是偶数这个条件可不能忘。

对于有向图就有点不同啦，要是每个顶点的入度和出度相等，那这个有向图就存在欧拉回路。

我做过这样的尝试，拿一个简单的三角形加箭头的有向图，每个顶点我都让它的入度和出度都是1，尝试着从一个顶点出发顺着箭头方向走，是能够走回原点的，这就表示是有欧拉回路的。

那要是入度和出度不相等呢，你可以想象一下，一个顶点进去的路和出去的路都不一样多，肯定没法形成回路把每条边都走过一次。

再来说构造方法，当我们确定一个图存在欧拉回路之后，构造其实可以用一种叫弗勒里算法的东西。

我整这算法的时候可费了不少劲呢。

我理解的这个算法，就像是一个很小心的旅行者，每次都沿着一条还没走过的边去下一个顶点，但是又不会走到那种会把剩下的边分成不连通部分的边，除非没有别的选择。

我一开始就是搞不懂这个‘不会走到那种会把剩下的边分成不连通部分’到底是什么意思，后来我就多做例子，好比有一个图看起来像蜘蛛网一样，我一步一步的按照这个规则走，终于明白了。

还有一点我忘说了，在无向图中，如果图是连通的，而且顶点度数都是偶数，我们就可以开始用这个构造方法啦。

不确定我的解释是不是完全清楚，但是这些都是我自己真的去摸索尝试得出来的一些经验，希望对你有帮助。