如何使用BFS找到循环图的直径？

Question

对于多个顶点大于5的循环图，在每个节点中运行BFS并从这些长度中选择一个最大值将停止工作。

例如：

​

以循环方式从1到6对每个顶点进行编号。

现在，使用BFS：-from节点1：

1. 取出节点1，在队列中添加2和6，将长度增加1。
2. 取出节点2，在队列中添加3，将长度增加1。
3. 取出节点6，在队列中添加5，将长度增加1。
4. 取出节点3，在队列中添加4，增加长度1。
5. 取出节点5，什么也不做
6. 取出节点4，什么也不做

长度已经等于4，这比直径还要大。

Answer 1

BFS在您的示例中确实找到了正确的直径。

它采用两条不同的路径：<1, 2, 3, 4>和<1, 6, 5>。

取最长的路径，即<1, 2, 3, 4>，取第一个节点与最后一个节点之间的距离，即路径中的节点数减去1，给出4-1=3，它是循环图的直径。