我们小时候可能就玩过“一笔画”的游戏在图论问题中我们时常会遇到需要遍历图中所有边的情况。例如邮递员规划一条不重复经过街道的送信路线。你可能会想到用 DFS 暴力搜索但边数一旦达到 (10^5) 级别回溯的代价将无法承受。那么是否存在一种方法既能在线性时间内判断这样的路径是否存在又能高效地将其构造出来呢数学家欧拉在 1736 年研究“哥尼斯堡七桥问题”时就给出了答案——这就是欧拉路径。欧拉路径以及它的特殊形式欧拉回路处理的正是“一笔画”问题从某点出发经过每条边恰好一次。它凭借简洁的判定条件和精巧的构造算法在邮件投递、电路设计、序列生成等众多领域成为首选工具。本文参考https://www.bilibili.com/video/BV1zFryBxEVJ/1.欧拉路径及其判定(1)什么是欧拉路径简单来说就是“一笔画”问题经过所有的边且每条边只经过一次形成的图其中起点和终点是同一个点的叫做欧拉回路不是一个点的称作欧拉路径(2)有向图存在欧拉回路的判定及证明判断条件忽略入度和出度都为0的点之后剩余的图①图上每个点都有入度 出度②是强连通图构造性的证明①我们从一个点s出发走到无法再前进的时候一定会再回到s这就形成了一条主线②其他未经过的边由于是强连通图一定可以参照第一步的方法形成一个环这就形成一条支线③把所有支线插入到主线里例如a - b - d 且有b - c - b则插入后有a - (b - c - b) - d这就形成了一条欧拉回路主线就像是一个大环而大环上又有很多个小环当大环开始绕的时候碰到小环入口就穿一圈小环回来再继续走(3)有向图存在欧拉路径的判定①去除入度和出度都为0的点剩下的点除了起点和终点都有入度出度②有且只有一个起点和终点起点满足出度 入度 1终点满足入度 出度 1③终点向起点引一条线判断有没有欧拉回路就可以了(3)无向图存在欧拉回路/路径的判定①忽略度为0的点剩下的点连通②统计度为奇数的点的数量记为odd③如果odd为0说明存在欧拉回路④如果odd为2说明存在欧拉路径⑤否则都不存在如果度为奇数那么经过的时候只有可能两种情况只出不进和只进不出如果是欧拉回路的话所有点有进和相同的出odd一定为0如果是欧拉路径除了起点和终点其他点也同理起点终点无所谓方向但度一定为奇数所以odd为22.欧拉路径的构造方法(1)有向图欧拉路径\回路的起点寻找①初始化start和end为-1首选遍历入度和出度如果出现差的绝对值大于1/入-出为1但end已赋值/出-入为1但start已赋值说明不存在直接返回-1②遍历完后如果start和end只有一个是-1也不存在返回-1③如果start不是-1直接返回start否则找到第一个出度大于0的返回找不到则返回-1(2)无向图欧拉路径\回路的起点寻找①初始化odd遍历统计度为奇数的点数②若不为0也不为2直接返回-1③否则如果是0返回第一个度大于0的④如果是2返回第一个度为奇数的⑤都找不到返回-1(3)有向图的Hierholzer算法希尔霍尔策算法采用了一种很巧妙的做法让没有回路的边先被记录要想实现我们只需从起点开始dfs遍历的时候记录或者直接删除遍历过的边如果无路可走也就是没有回路了就直接压入答案数组知道该点的出边全部遍历或者删除完则结束进程并反转答案注意反转后还需要判断ans长度是否为边数-1证明能遍历所有边即为欧拉路径/回路如图从a开始a-b-c-d没路了d压入答案返回到c也没路可走继续压入返回到bb-e-f-b-g-h-b没路可走压入b同理依次压入h,g,b,f,e,b,a反转后得到abefbghbcd即为欧拉路径如果需要输出字典序最小的只需要对邻接表进行排序就可以希尔霍尔策算法的递归版十分简洁只需要8行时间复杂度为O(mn)需要排序则为O((mn)logm)例题链接 https://www.luogu.com.cn/problem/P7771示例代码如下#includebits/stdc.husingnamespacestd;usinglllonglong;constintMOD1e97;intn,m;vectorvectorintadj;vectorintin,out;intfindStart(){intstart-1,end-1;for(inti1;in;i){intvout[i]-in[i];if(v-1||v1||(v1start!-1)||(v-1end!-1))return-1;if(v1)starti;if(v-1)endi;}// 确定有无起点终点if((start-1)^(end-1))return-1;// 只有一个则不存在if(start!-1)returnstart;// 欧拉路径for(inti1;in;i){if(out[i]0)returni;// 欧拉回路}return-1;// 没有边}vectorintans;voideuler(intu){while(!adj[u].empty()){intvadj[u].back();adj[u].pop_back();// 删边euler(v);}ans.push_back(u);// 无路可走就压入}intmain(){ios::sync_with_stdio(false);cin.tie(0);cinnm;intu0,v0;adj.resize(n1);in.resize(n1,0);out.resize(n1,0);for(inti0;im;i){cinu0v0;adj[u0].push_back(v0);out[u0];in[v0];// 计算入度和出度}for(inti1;in;i){sort(adj[i].begin(),adj[i].end(),greaterint());// 每次都遍历并删除后面路径要使字典序最小需要从大到小排序}intsfindStart();if(s-1){coutNo;return0;}euler(s);if(ans.size()!m1){// 没有遍历所有边则不存在coutNo;return0;}reverse(ans.begin(),ans.end());// 反转后即为答案for(intan:ans)coutan ;return0;}(4)无向图的Hierholzer算法与有向图的思想完全一样但需要注意的是无向图每条边都是双向的但是每条边只能使用一次因此邻接表需要多一个位置记录边的编号并使用used标记同时因为没有删边操作理论上每次遍历边时会一直从头遍历所有需要一个弧指针cur来标记每个点进行到了哪条边并在遍历时同步自增核心代码如下#includebits/stdc.husingnamespacestd;usinglllonglong;constintMOD1e97;intn,m;vectorvectorpairint,intadj;// (v, edge_id)vectorboolused;vectorintdeg,ans,cur;// cur 是当前弧指针intunFindStart(){intodd0;// 记录度为奇数的点的数量for(inti1;in;i){if(deg[i]1)odd;}if(odd!0odd!2)return-1;// 0存在欧拉回路2存在欧拉路径否则不存在for(inti1;in;i){if(odd0deg[i]0)returni;if(odd2(deg[i]1))returni;}return-1;}voideuler(intu){for(inticur[u];iadj[u].size();){// i引用cur[u]与其同步自增auto[v,e]adj[u][i];if(used[e])continue;// 每条边只能用一次used[e]true;euler(v);}ans.push_back(u);}3.欧拉路径的应用构造 De Bruijn 序列例题链接https://vjudge.net/problem/CSES-1692#authortranslator:1281311:zh此处是二进制的例子事实上序列可以推广到k进制此处仅拿2进制说明(1)构造 De Bruijn 序列的思路要构造这样一个序列位数是n那么最好的情况也就是序列的最短长度首先需要2^n作每个子串的开始其次最后需要n-1个序列结束最后一个子串这是最紧密的情况那么我们怎么保证能最小构造出来且需要不重不漏呢事实上每个n位子串可以拆分n-1位子串和最后一位对每个n-1位子串最后一位又只能是0或1若k进制只能是0,1,2…k-1下同理很显然这样拆分可以不重复的包括所有n位子串那么我们只需要以n-1位子串为点0和1为边构造一张图这样每条边都表示一个子串边的关系为经过的边后置并去掉最前面一位如010通过边1到达101那么n-1位子串通过之前的出边变为了一个n位子串同时去掉第一位就变成了一个新的n-1位子串重复上述过程就可以显然只需要不重复的遍历所有边那么起点加上路径就是最终答案于是我们自然而然想到了欧拉回路(由于每个点的入边和出边都只有0和1两条所以图一定是也只能是欧拉回路)那么我们进行希尔霍尔策算法时用十进制表示每个点还需要加一个参数边把边压入路径数组里同时还应该使用弧优化记录当前是边0还是边1(从小到大记录的弧优化如果起点从0开始可以保证最后的字符串是最小字典序)假设是边x(x0,1)那么下一条边u首先要后置x即u u 1 x,如果要去掉最后一位呢因为u是十进制可以表示成 x1 * (2^n-1) x2 * (2^n-2) … xn * (2^0)要想去掉最后一位只需要对(2^n-1)取模即可例如下图从00开始。初始序列是00边0构造子串000去掉前面一位到达00序列000边1构造子串001去掉前面一位到达01也如图所示此时序列0001再走边0后移一位到达10此时序列00010以此类推最后得到0001011100注意上述过程不是希尔霍尔策的算法是按照欧拉回路走的过程希尔霍尔策算法的运行过程这里不做赘述参考前面的模版即可(2)构造 De Bruijn 序列的示例代码#includebits/stdc.husingnamespacestd;usinglllonglong;constintMOD1e97;intn,m;// n为位数m为点的个数m为2的n-1次方也是cur数组的长度vectorintpath,cur;voideuler(intu,inte){for(inticur[u];i2;){intnei;euler(((u1)ne)%m,ne);}path.push_back(e);// 无路可走就压入}intmain(){ios::sync_with_stdio(false);cin.tie(0);cinn;m1(n-1);cur.resize(m1,0);euler(0,-1);path.pop_back();// 弹出-1reverse(path.begin(),path.end());// 反转后即为答案for(inti0;in-1;i)cout0;for(intan:path)coutan;return0;}4. 总结欧拉路径是一种思路清晰、实现简洁的图论算法。处理这类问题时通常遵循以下流程判定存在性有向图检查每个点的入度与出度之差。欧拉回路要求所有点入度等于出度欧拉路径要求恰有一个起点出度 入度 1和一个终点入度 出度 1其余点入度等于出度且忽略零度点后图强连通无向图统计奇数度点的个数。回路要求奇数度点数为 0路径要求恰好为 2同时忽略零度点后图连通寻找起点欧拉回路可从任意有边的点出发欧拉路径必须从出度比入度大 1有向图或度数为奇数无向图的点出发构造路径Hierholzer 算法从起点开始 DFS每走一条边就将其删除直到当前点无路可走才将该点压入答案栈最后逆序输出有向图可以直接删边无向图因为每条边存储两次需要配合“弧优化”跳过已标记的边应用与变种求字典序最小的欧拉路径只需对邻接表排序后再遍历构造 De Bruijn 序列时将 (n) 位子串建模成 (n-1) 位节点与 0/1 边的图求欧拉回路即可生成最短的包含所有子串的序列不同题目中判定与构造的框架基本不变重要的是理解 Hierholzer 算法“逆序记录”的精妙之处它让无法继续的支线先被记录从而保证所有环都能正确嵌入主线路径。掌握了这个思想无论是单纯的路径输出还是复杂的序列生成建模都能迎刃而解