Search code examples
algorithmdata-structuresgraph

Finding length of shortest cycle in undirected graph

I tried the following :

1) DFS, keeping track of level of each vertex in my DFS tree

2) Each time a back edge (x,y) is seen, I calculate cycle length = level[x] - level[y] + 1, and save it if it is smaller than the shortest

Can someone tell a counter example for which this approach is wrong ?

What could be a better way to find shortest cycle in undirected graphs ?

Thanks.

Solution

  • Why DFS won't work

    You cannot use DFS to find a shortest circle. We can easily create a counter example, where DFS leads finds only the longest circle. Lets have a look at the following graph:

    A graph with a "long line"

    As you can see we have nine nodes. If we start at the leftmost node A, the following DFS level could be possible:

    Resulting depth first search tree

    We have two back edges while iterating:

    • (B , A), therefore we found a circle with length 8
    • (D , A), therefore we found a circle with length 8

    However, the shortest circle has length 5. It's shown in blue in the next picture, whereas one of the previously found circles is shown in red:

    Long circle vs. short circle

    You didn't see the blue circle because your DFS path doesn't contain it. Dagupa et al also mention this behaviour in their book:

    But it also means that DFS can end up taking a long and convoluted route to a vertex that is actually very close by.

    Why BFS won't work

    Well, that's not entirely true, one can use BFS (see next subsection), but you cannot use your formula. Take the following graph:

    No fancy picture for this graph yet.

Every "o" is a node.

        o---o
        |   |
+-------o---o-------+
|                   |
o----o----o----o----o

    Lets see what levels are possible in BFS. If I start at the node in the middle, I get the following levels:

            5~~~5            ~~~ are back-edges
        |   |
+-------4~~~4-------+
|                   |
3----2----1----2----3

    And if I start at the left node, I get the following levels:

            3~~~4
        |   |
+-------2---3-------+
|                   |
1----2----3----4~~~~4

    Therefore, you cannot use your level formula.

    Solution

    Although not efficient, using an all-pair shortest path algorithm and checking the distance (i,i) for every node is a valid solution.