Некоторые алгоритмы для поиска диаметра графа:

1. Алгоритм, основанный на BFS. 1 Для каждой вершины v в графе G выполнить BFS(v) и построить двумерный массив расстояний от каждой вершины до других. 1 Затем вычислить e(v) для каждой вершины из созданного на первом этапе массива и найти диаметр графа, вычислив максимальное значение e(v). 1
2. Алгоритм, работающий за линейное время O(V + E). 1 Выполнить BFS на любой случайной вершине v ∈ V(G), выбрать вершину u с максимальным расстоянием, снова выполнить BFS на этой вершине u и определить диаметр как максимальное расстояние, полученное на третьем этапе. 1
3. Алгоритм приближённой функции окрестности (Approximate Neighborhood Function Algorithm). 2 Позволяет приближённо вычислить радиус и диаметр графа, при этом поиск расстояний между вершинами графа производится с некоторой погрешностью, что помогает уменьшить время счёта. 2