gpt4 book ai didi

algorithm - 有向图 : Euler Path

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:37:59 24 4
gpt4 key购买 nike

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

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

[图片来源:geeksforgeeks.org]

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

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

  1. 如果从顶点 0 开始我的 DFS,我仍然有欧拉路径。
  2. 如果从顶点 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/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com