图直径算法求教

关于这个经典的图直径算法，我有一个反例不知道怎么理解。


To find the diameter of a graph using BFS, follow these steps:

• Choose any node, source, in the graph.
• Run BFS from source to compute the shortest path to every other node in the graph.
• Find the node, farthest_node, with the maximum shortest path distance from source.
• Run BFS again from farthest_node to compute the shortest path to every other node.
• The maximum shortest path distance found during the second BFS iteration represents the diameter of the graph.

The BFS algorithm guarantees that we visit all nodes in breadth-first order, ensuring that we find the shortest path between any two nodes efficiently.


reference: https://saturncloud.io/blog/algo...or-data-scientists/


反例是这样的：


2 - 4 - 1 - 5
         \     /
           3


如果在第一步choose any source的时候选择了 1，那第3步的farthest_node就可以是2或者3。这时候，如果我们选择3作为起点开始跑第二个BFS，就会得到错误的结论——该图的直径为2。求教我在哪一步理解错了，还是说farthest_node有tie的时候，有特殊操作？

对于有环图，链接的方法很明显是错的。
我觉得应该用All pairs shortest path的算法。

3为起点的BFS，最远的不是5吗？

链接的解法应该只适用于树图（树任意两点间就一条路，可以用这个性质反证）。

这是算树的直径

https://oi-wiki.org/graph/tree-diameter/