Определение диаметра графа

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Диаметром неориентированного графа называется максимальная длина кратчайшего пути между двумя вершинами. Классический способ определения диаметра – выполнить поиск в ширину от всех вершин, тогда диаметр равен максимальному из найденных расстояний. Сложность такого подхода составляет $O(mn)$, и в худшем случае (например, когда граф является циклом) эту оценку, по-видимому, улучшить нельзя.

Алгоритм iFUB (англ. iterative Fringe Upper Bound) позволяет уменьшить количество вызовов алгоритма поиска в ширину. Для многих реальных графов будет достаточно всего нескольких вызовов и общая сложность будет близка к линейной $O(m)$.

1.6 Последовательная сложность алгоритма

Последовательная сложность алгоритма iFUB равна $O(Bm)$, где $B$ – число вызовов алгоритма поиска в ширину, сложность каждого вызова $O(m)$. В худшем случае (граф является циклом) $B = n$ и общая сложность равна $O(mn)$, однако для многих реальных графов $B = O(1)$ и общая сложность составляет $O(m)$.

1.9 Описание входных и выходных данных

Входные данные: неориентированный граф $(V, E)$ ($n$ вершин $v_i$ и $m$ рёбер).

Объём входных данных: $O(m + n)$.

Выходные данные: диаметр графа $(V, E)$.

Объём выходных данных: $O(1)$.

2 Программная реализация алгоритмов

2.7 Существующие реализации алгоритма

• Java: WebGraph (класс FourSweepIterativeFringeDiameter), многопоточная реализация. Алгоритм был использован для вычисления диаметра подграфа социальной сети Facebook (149 миллионов вершин, 16 миллиардов рёбер), время работы составило 20 минут.
• Python/C++: NetworKit (класс networkit.properties.Diameter).