Можно ли использовать BFS для определения самой дальней вершины?

Question

Можем ли мы использовать алгоритм BFS для определения самой далекой вершины от начальной вершины v в любом графе с точки зрения количества ребер.

Answer 1

Да.Назовем расстояние от узла A до узла B числом ребер от A до B. BFS находит все узлы расстояния 1, затем все узлы расстояния 2 и так далее.Чтобы найти самую дальнюю вершину, просто сохраните последний искомый узел, потому что он определил самое длинное расстояние.