6
$\begingroup$

We wish to find shortest cycle (if any cycle exists) that includes a special vertex $v$.

We know if we run DFS on an undirected graph, back edges show us that there exists at least one cycle.

This answer on SO explains why neither BFS or DFS work. However, I still think that DFS could be helpful in finding a minimun such cycle. Is there a way to make it work?

$\endgroup$
2
  • 2
    $\begingroup$ That seems to be explained in the SO post as well. I don't see what your question is now. Community votes, please: unclear? $\endgroup$
    – Raphael
    May 20 '16 at 12:32
  • $\begingroup$ @Shaull I tried hard to solve it with DFS It might be cause of that I didn't see how BFS works well. Thanks. $\endgroup$
    – Niloo
    May 20 '16 at 14:21
8
$\begingroup$

You can find the shortest cycle that contains $v$ by running BFS from $v$, and stopping at the first time that $v$ is reached again (or if BFS terminated without reaching $v$).

An important property of BFS is that if it runs from vertex $v$, then every vertex $s$, when it is first reached, then the path that was found from $v$ to $s$ is minimal. Thus, reaching $v$ from $v$ with BFS finds the shortest path from $v$ to itself, namely the shortest cycle that contains $v$.

$\endgroup$
2
  • $\begingroup$ I think your algorithm only works when the underlying graph is directed $\endgroup$
    – Null_Space
    Jun 17 at 20:50
  • $\begingroup$ @Null_Space - an undirected graph is a special case of a directed graph (with the edge relation is symmetric). Also, an undirected graph has a cycle iff it has an edge, because you can go back and forth. $\endgroup$
    – Shaull
    Jun 18 at 6:00

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.