首先，我不会说谎。这是我的作业。我花了太多时间来解决这个问题，但我一点头绪都没有。
我需要编写算法(高效)来找到从给定顶点到所有其他顶点具有偶数长度路径的所有顶点。
我知道它可能与 DFS 用途有关...
请给我一些指导!
最佳答案
由于是作业，我只是提供一些提示:
- 如果您在不维护
visited的情况下进行一定深度的 DFS设置 - 您“发现”的所有顶点都有来自源的路径，长度等于当前深度。 - 如果你进行 DFS 到深度
2|V|，所有从源开始的路径长度为偶数的顶点都将在某个偶数深度级别被发现。 [说服自己为什么:奇数周期会发生什么？偶数长度周期会发生什么？]
注意:运行时间是顶点数量的指数[加倍]。
关于algorithm - 偶长路径算法-DFS，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10062814/