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

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

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

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

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

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

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

Входные и выходные данные алгоритма

Входные данные: неориентированный граф [math]\displaystyle{ (V, E) }[/math] ([math]\displaystyle{ n }[/math] вершин [math]\displaystyle{ v_i }[/math] и [math]\displaystyle{ m }[/math] рёбер).

Объём входных данных: [math]\displaystyle{ O(m + n) }[/math].

Выходные данные: диаметр графа [math]\displaystyle{ (V, E) }[/math].

Объём выходных данных: [math]\displaystyle{ O(1) }[/math].