Even the length path algorithm -DFS
First, I will not lie. This is my homework. I am trying to solve this issue too much and I have no idea.
I need to write an algorithm (efficient) that will find all vertices with an even path from a given vertex to all other vertices.
I know its probably something using DFS ...
Please give me some tips!
source to share
Since this is homework, I only provide some hints:
- If you DFS to a certain depth without maintaining a set
visited
, all the vertices you "discover" have a path from the source that is the same length as the current depth. - If you DFS to depth
2|V|
, all vertices with length paths from the source will be detected at a specific depth level. [convince yourself why: what happens for an odd-length cycle? what happens for a cycle of even length?]
Beware: Runtime exponentially in number of vertices [doubles].
source to share
For each node, I create 3 boolean states
(I, 0): uncovered
(i, 1): an odd length can be reached
(i, 2): an even length can be achieved
first they are all zeros
then you do dfs, you can change inside dfs the node states you are visiting, if you find that you are not changing the node state, then stop that thread.
Because there are totally 3 * n states that you can change, so the maximum time you need is O (m) s - the number of edges ~
source to share
Are you concerned about opening times? Was this discussed? Have you talked about efficient data structures for sets? If not, then a hint will help you.
If so, then you must be smarter. You talked about storing a set of previously visited vertices when you discussed DFS, right?
Instead, you can support more than one set with each set, which means something slightly different. You could imagine that your visited set is a union of these separate sets, but critically you may need to revisit a vertex if it appears in one and then appears in another later.
Ask yourself: What rigs can I place on the vertices? If a vertex is already attached to some set by visiting it, when might I need to revisit it? Be careful, you can easily make a mistake here.
source to share