基于标准定义，Eulerian Path是图中的一条路径，它恰好访问每条边一次。
现在，我试图在有向图中找到欧拉路径。我知道欧拉电路的算法。如果一个图有欧拉回路，它就有欧拉路径，这似乎是微不足道的。 
[图片来源:geeksforgeeks.org]
所以对于上面有欧拉回路的有向图也有欧拉路径。
现在，如果我删除一条边，假设从 4 到 0，它不再是欧拉电路。
- 如果从顶点 0 开始我的 DFS，我仍然有欧拉路径。
- 如果从顶点 3 开始我没有欧拉路径
那么，有向图是否必须在欧拉电路中才能成为欧拉路径？我想，欧拉路径应该比欧拉回路限制更少。
有没有可以是欧拉路径但不是欧拉回路的有向图？
最佳答案
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 并找到一条欧拉路径。
关于algorithm - 有向图 : Euler Path，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27584381/