0

A shortest cycle is one with the minimum number of edges.

For example, given a graph:

enter image description here

The shortest cycles are: ACDA, DABD

If I only needed to find one shortest cycle, I would just run BFS on every vertex and keep track of the smallest cycle. But I don't know how to enumerate all smallest cycles.

There is a similar SO question on enumerating minimal cycles in a digraph, but there a minimal cycle is one which is not a union of smaller cycles. Here I am only looking for the cycles with the minimum number of edges.

Community
  • 1
  • 1
vladimirm
  • 261
  • 1
  • 2
  • 8

1 Answers1

0

Run a number of DFS searches as in topological sort: start from a random vertex, and continue running new DFS searches as long as there are some unexplored vertices.

In a search, as soon as you find a back edge, you know that (1) there's a cycle (2) the number of edges in that cycle. If you also need to get a list of edges in the cycle, keep an array for each "currently detected cycle" and fill it as you backtrack in the DFS call graph. If the back-edge was a node A->B, When you'll reach back node B, the array is going to contain all edges in the cycle.

Of course, keep in track the "shortest cycle found so far" to avoid bookkeeping edge lists for cycles that are longer than this minimum.

kfx
  • 8,136
  • 3
  • 28
  • 52