Визначення діаметра графа

Зміст

1 Властивості та структура алгоритму

1.1 Загальний опис алгоритму

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

АлгоритмiFUB[1] (англ.iterativeFringe Upper Bound) дозволяє зменшити кількість викликів алгоритму пошуку завширшки. Для багатьох реальних графів буде достатньо декількох викликів і загальна складність буде близька до лінійної [math]O(m)[/math] .

1.2 Математичне опис алгоритму

1.3 Обчислювальне ядро ​​алгоритму

1.4 Макроструктура алгоритму

1.5 Схема реалізації послідовного алгоритму

1.6 Послідовна складність алгоритму

Послідовна складність алгоритмуiFUB дорівнює [math]O(Bm)[/math] , де [math]B[/math] – кількість викликів алгоритму пошуку завширшки, складність кожного виклику [math]O(m )[/math] . У найгіршому випадку (граф є циклом) [math]B = n[/math] і загальна складність дорівнює [math]O(mn)[/math] , проте для багатьох реальних графів [math]B = O(1)[/ math] та загальна складність складає [math]O(m)[/math] .

1.7 Інформаційний граф

1.8 Ресурс паралелізму алгоритму

1.9 Вхідні та вихідні дані алгоритму

Вхідні дані: неорієнтований граф [math](V, E)[/math] ([math]n[/math] вершин [math]v_i[/math] та [math]m[/math] ребер).

Обсяг вхідних даних: [math]O(m + n)[/math] .

Вихідні дані: діаметр графа [math](V,E)[/math] .

Обсяг вихідних даних: [math]O(1)[/math] .

---