Skip to content

欧拉路 笔记 ​

还有 15 天退役不会找欧拉路径!??!

先找到起点:

  • 无向图:度数为奇数的点(2 个分别为起点终点)。
  • 有向图:入度出度恰好差 1 的点,其他点应入度出度完全相同。

然后从起点开始 DFS。

遍历 (u,v),当 dfs(v) 完成后,将这条边放入路径。

为了防止多次遍历重复的边浪费时间,我们需要记录每个点已经遍历过哪些边,下次再访问到这个点就从这条边开始遍历。

最近更新