Consider this example, I did my pseudocode in python

    for each edge e in E(G):
        if isThereCycle(G-e):
            G = G - e
    return G 

assume isthereCycle returns whether the graph $G$ has a cycle.

Input is a graph $G$ that contains a cycle, and the function should return a path of that cycle.

We go through each edge then remove it and see if a cycle still exists without that edge, until we are left with a graph with a single path that is a cycle. (Assume removing the edge (G - e) doesn't mutate the graph unless we do G = G - e).

I want to return a path. Is what I'm returning a path?

  • $\begingroup$ You return a graph without a cycle which is a forest. If $G$ is a forest in the very beginning, you would return it. $\endgroup$ – Eugene Jul 21 '19 at 23:20
  • $\begingroup$ How am I returning a graph without a cycle when I only remove edges that don't effect the cycle?(Assuming G does have a cycle) $\endgroup$ – Tree Garen Jul 21 '19 at 23:23
  • $\begingroup$ The question was if you return a path. The answer is no. Why? Because if the input is a forest, it is returned unmodified. I am not sure if there are more questions. $\endgroup$ – Eugene Jul 21 '19 at 23:37

Your algorithm returns a cycle rather than a path.

Here is a cycle:


Here is a path:


(Both images taken from Wikipedia.)

To get a path from the cycle, simply remove one edge (this is my best guess for what return a path of that cycle means).

Let me also mention that your algorithm is very inefficient. A much better choice is to use BFS/DFS.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.