algorithm - 有向图 : Euler Path

Question

基于标准定义，Eulerian Path是图中的一条路径，它恰好访问每条边一次。

现在，我试图在有向图中找到欧拉路径。我知道欧拉电路的算法。如果一个图有欧拉回路，它就有欧拉路径，这似乎是微不足道的。

[图片来源:geeksforgeeks.org]

所以对于上面有欧拉回路的有向图也有欧拉路径。

现在，如果我删除一条边，假设从 4 到 0，它不再是欧拉电路。

1. 如果从顶点 0 开始我的 DFS，我仍然有欧拉路径。
2. 如果从顶点 3 开始我没有欧拉路径

那么，有向图是否必须在欧拉电路中才能成为欧拉路径？我想，欧拉路径应该比欧拉回路限制更少。

有没有可以是欧拉路径但不是欧拉回路的有向图？

Answer 1

So, is it a requirement, that a directed graph has to be in Euler circuit to be an Euler path?

没有

I thought, Euler path should be less restrictive than Euler circuit.

正确

Is there any directed graph which can be Euler path but not Euler circuit.

是

我相信您的困惑源于以下事实:当您从不同节点开始对有向图进行 DFS 时，您可能会得到不同的结果，因为当您从不同节点开始时，某些节点可能无法访问。这与欧拉路径/轨迹的定义无关。为了在有向图中“实现”欧拉路径搜索，您应该从每个节点运行 DFS - 并且只有当所有结果都返回 False(未找到欧拉路径)时，您才能确定不存在欧拉路径.如果存在欧拉环路，则必须有一个节点，您可以从该节点开始 DFS 并找到一条欧拉路径。