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