无向图的Hierholzer算法流程（二）

精妙的深度优先搜索虽然 Hierholzer 算法的流程看起来较为复杂但我们可以通过一段精妙的代码将算法流程中的两个步骤合并到同一个深度优先搜索过程中。在图论的代码实现中一条无向边一般会被拆成两条有向边。由于 Hierholzer 算法的流程需要我们删除一条无向边因此我们需要同时删除一条有向边和它的反向边。这样的操作只有利用链式前向星^6亦称边表存储无向图时才能在 的时间复杂度内完成因此下文的代码实现中均使用链式前向星存储无向图。Hierholzer 算法的一个 C 实现如下。请注意为了便于分析与讲解下面给出的代码实现并不是欧拉回路的最优时间复杂度实现。下文中我们将提出该实现的一个优化。// 为了方便存储一条边的众多信息我们定义一个结构体 // // struct Edge { // int fn, nxt; // bool del; // }; // // 其中 // * fn 表示这条有向边的终点 // * nxt 表示链式前向星中该有向边的后续边的编号如果没有后续边则值为 0 // * del 表示这条边是否被遍历过了 // // e[] 是一个类型为 Edge 的数组e[i] 表示链式前向星中编号为 i 的边 // p[] 是一个类型为 int 的数组p[i] 表示以 i 为起点的第一条边在链式前向星中的编号 // 如果没有以 i 为起点的有向边则 p[i] 的值为 0 // // 为了方便我们查找某一条有向边的反向边当我们向链式前向星中加入第 ii 从 1 到 m条无向边 x - y 时 // 我们会将有向边 x - y 存储在 e[i * 2]有向边 y - x 存储在 e[i * 2 1] // 这样e[i] 和 e[i ^ 1] 就互为反向边 // // ans 是一个类型为 vectorEdge 的变量用来存储我们找到的回路 void dfs(int sn) { for (int i p[sn]; i ! 0; i e[i].nxt) { // 这条边已经被遍历过了跳过 if (e[i].del) continue; // 删除有向边 e[i] 和它的反向边 e[i ^ 1] e[i].del e[i ^ 1].del true; // 继续遍历相邻点 dfs(e[i].fn); // 将边 e[i] 加入结果序列中 ans.push_back(e[i]); } }调用dfs(S)后ans里就保存了从节点S出发并回到节点S的欧拉回路。需要注意的是此时ans中保存的欧拉回路是我们求出的欧拉回路的倒序。因此我们还需要调用reverse(ans.begin(), ans.end())将ans中所有元素顺序倒转后才能得到我们想要的欧拉回路。