我们小时候可能就玩过“一笔画”的游戏，在图论问题中，我们时常会遇到需要遍历图中所有边的情况。例如，邮递员规划一条不重复经过街道的送信路线。你可能会想到用 DFS 暴力搜索，但边数一旦达到 (10^5) 级别，回溯的代价将无法承受。那么，是否存在一种方法，既能在线性时间内判断这样的路径是否存在，又能高效地将其构造出来呢？ 数学家欧拉在 1736 年研究“哥尼斯堡七桥问题”时就给出了答案——这就是 欧拉路径 。欧拉路径（以及它的特殊形式欧拉回路）处理的正是“一笔画”问题：从某点出发，经过每条边恰好一次。它凭借简洁的判定条件和精巧的构造算法，在邮件投递、电路设计、序列生成等众多领域成为首选工具。 （本文参考：https://www.bilibili.com/video/BV1zFryBxEVJ/） 简单来说就是“一笔画”问题：经过所有的边，且每条边只经过一次，形成的图 其中起点和终点是同一个点的，叫做 欧拉回路 ，不是一个点的，称作 欧拉路径 (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为2 (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，也没路可走，继续压入返回到b，b-e-f-b-g-h-b没路可走，压入b，同理，依次压入h,g,b,f,e,b,a反转后得到abefbghbcd，即为欧拉路径 如果需要输出字典序最小的，只需要对邻接表进行排序就可以 希尔霍尔策算法的递归版十分简洁，只需要8行，时间复杂度为O(m+n)，需要排序则为O((m+n)logm) 例题链接 https://www.luogu.com.cn/problem/P7771 示例代码如下 (4)无向图的Hierholzer算法 与有向图的思想完全一样，但需要注意的是，无向图每条边都是 双向的 ，但是每条边只能 使用一次 ，因此，邻接表需要多一个位置记录边的编号，并使用used标记，同时，因为没有删边操作，理论上每次遍历边时会一直从头遍历，所有需要一个 弧指针 cur来标记每个点进行到了哪条边，并在遍历时同步自增，核心代码如下 3.欧拉路径的应用：构造 De Bruijn 序列 例题链接：https://vjudge.net/problem/CSES-1692#author=translator: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(x=0,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 序列的示例代码 欧拉路径是一种思路清晰、实现简洁的图论算法。处理这类问题时，通常遵循以下流程： 判定存在性 ： 有向图：检查每个点的入度与出度之差。欧拉回路要求所有点入度等于出度；欧拉路径要求恰有一个起点（出度 = 入度 + 1）和一个终点（入度 = 出度 + 1），其余点入度等于出度，且忽略零度点后图强连通 无向图：统计奇数度点的个数。回路要求奇数度点数为 0，路径要求恰好为 2，同时忽略零度点后图连通 寻找起点 ： 欧拉回路可从任意有边的点出发 欧拉路径必须从出度比入度大 1（有向图）或度数为奇数（无向图）的点出发 构造路径（Hierholzer 算法） ： 从起点开始 DFS，每走一条边就将其删除，直到当前点无路可走才将该点压入答案栈，最后逆序输出 有向图可以直接删边；无向图因为每条边存储两次，需要配合“弧优化”跳过已标记的边 应用与变种 ： 求字典序最小的欧拉路径，只需对邻接表排序后再遍历 构造 De Bruijn 序列时，将 (n) 位子串建模成 (n-1) 位节点与 0/1 边的图，求欧拉回路即可生成最短的包含所有子串的序列 不同题目中判定与构造的框架基本不变，重要的是理解 Hierholzer 算法“逆序记录”的精妙之处：它让无法继续的支线先被记录，从而保证所有环都能正确嵌入主线路径。掌握了这个思想，无论是单纯的路径输出，还是复杂的序列生成建模，都能迎刃而解 openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构 · HarmonyOS 应用开发核心技术与上架分发概览 · Go 文件与 IO 操作知识点总结：操作系统底层、源码原理与 bufio 流式高性能实战 · 7 OSEK OS Alarm/8 Messages HarmonyOS 应用开发核心技术与上架分发概览 Go 文件与 IO 操作知识点总结：操作系统底层、源码原理与 bufio 流式高性能实战 7 OSEK OS Alarm/8 Messages 为遵守国家网络实名制规定，未绑定将限制内容发布与互动