即使长路径算法-DFS [英] Even length path algorithm -DFS

问题描述

首先，我不会说谎。这是我的家庭作业。我特林解决这一问题太多小时，我不知道。

First, I won't lie. This is my homework. I'm tring to solve this question for too many hours and I have no clue.

我需要写算法（效率）的找到所有与偶数路径长度从给定的顶点到所有其他顶点顶点。

I need to write algorithm ( efficient) that find all the vertices with a even-length path from a given vertex to all other vertices.

我知道它可能是一些与DFS使用...

I know its probably something with DFS uses...

请给我一些指导！

推荐答案

既然是家庭作业，我只是提供了一些提示：

Since it is homework, I am only providing some hints:

1. 如果你做一个DFS达到一定的深度，不维护一个访问设置 - 所有的顶点，你发现具有路径从源头，长度等于当前深度。
2. 如果你做一个DFS高达深度 2 | V | ，所有从源头甚至长路径的顶点将被发现在有的甚至深度级别。 [说服自己为什么：奇数长周期发生了什么？即使长周期发生了什么？]

1. If you do a DFS up to a certain depth, without maintaining a visited set - all the vertices you "discover" has path from the source, with length equals to the current depth.
2. If you do a DFS up to depth 2|V|, all the vertices with even-length paths from the source will be discovered in some even depth level. [convince yourself why: what happens for odd-length cycle? what happens for even-length cycle?]

当心：运行时间是指数的顶点数量[一倍]

Beware: running time is exponential in the number of vertices [doubled].

这篇关于即使长路径算法-DFS的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！