How can you find the diameter of a cyclic graph using BFS?

Question

For cyclic graphs with a number of vertices larger than 5, running BFS in each node and picking a maximum out of those lengths stops working.

For example:

Number each vertex from 1 to 6 in a cyclic manner.

Now, using BFS: -from node 1:

1. takes node 1 out, adds 2 and 6 in the queue, increases length by 1
2. takes node 2 out, adds 3 in the queue, increases length by 1
3. takes node 6 out, adds 5 in the queue, increases length by 1
4. takes node 3 out, adds 4 in the queue, increases length by 1
5. takes node 5 out, does nothing
6. takes node 4 out, does nothing

Length is already equal to 4, which is more than the diameter.

Answer 1

BFS does find the correct diameter in your example.

It takes two separate paths: <1, 2, 3, 4> and <1, 6, 5>.

You take the longest path which is <1, 2, 3, 4> and you take the distance between the first and the last node which is the number of nodes in the path minus 1. It gives 4-1=3 which is the diameter of the cycle graph.