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

Question

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

例如：

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

现在，使用 BFS：-从节点 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的是循环图的直径。