Определение диаметра графа: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [досмотренная версия] |
Daryin (обсуждение | вклад) |
ASA (обсуждение | вклад) |
||
| (не показаны 3 промежуточные версии 2 участников) | |||
| Строка 1: | Строка 1: | ||
| − | == Свойства и структура | + | {{level-a}} |
| + | |||
| + | == Свойства и структура алгоритма == | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| Строка 6: | Строка 8: | ||
'''Алгоритм ''i''FUB'''<ref>Crescenzi, Pilu, Roberto Grossi, Michel Habib, Leonardo Lanzi, and Andrea Marino. “On Computing the Diameter of Real-World Undirected Graphs.” Theoretical Computer Science 514 (November 2013): 84–95. doi:10.1016/j.tcs.2012.09.018.</ref> (англ. ''iterative'' Fringe Upper Bound) позволяет уменьшить количество вызовов алгоритма поиска в ширину. Для многих реальных графов будет достаточно всего нескольких вызовов и общая сложность будет близка к линейной <math>O(m)</math>. | '''Алгоритм ''i''FUB'''<ref>Crescenzi, Pilu, Roberto Grossi, Michel Habib, Leonardo Lanzi, and Andrea Marino. “On Computing the Diameter of Real-World Undirected Graphs.” Theoretical Computer Science 514 (November 2013): 84–95. doi:10.1016/j.tcs.2012.09.018.</ref> (англ. ''iterative'' Fringe Upper Bound) позволяет уменьшить количество вызовов алгоритма поиска в ширину. Для многих реальных графов будет достаточно всего нескольких вызовов и общая сложность будет близка к линейной <math>O(m)</math>. | ||
| − | === Математическое описание === | + | === Математическое описание алгоритма === |
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
| − | === | + | === Схема реализации последовательного алгоритма === |
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
| Строка 15: | Строка 17: | ||
=== Информационный граф === | === Информационный граф === | ||
| − | === | + | === Ресурс параллелизма алгоритма === |
| − | === | + | === Входные и выходные данные алгоритма === |
'''Входные данные''': неориентированный граф <math>(V, E)</math> (<math>n</math> вершин <math>v_i</math> и <math>m</math> рёбер). | '''Входные данные''': неориентированный граф <math>(V, E)</math> (<math>n</math> вершин <math>v_i</math> и <math>m</math> рёбер). | ||
| Строка 26: | Строка 28: | ||
'''Объём выходных данных''': <math>O(1)</math>. | '''Объём выходных данных''': <math>O(1)</math>. | ||
| − | === Свойства алгоритма=== | + | === Свойства алгоритма === |
| − | == Программная реализация | + | |
| + | == Программная реализация алгоритма == | ||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
| − | + | === Возможные способы и особенности параллельной реализации алгоритма === | |
| − | === Возможные способы и особенности реализации | + | === Результаты прогонов === |
| − | === | ||
| − | |||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
| − | |||
| − | |||
| − | |||
== Литература == | == Литература == | ||
<references /> | <references /> | ||
| + | |||
| + | [[Категория:Начатые статьи]] | ||
| + | |||
| + | [[en:Longest shortest path]] | ||
Текущая версия на 10:05, 7 июля 2022
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Диаметром неориентированного графа называется максимальная длина кратчайшего пути между двумя вершинами. Классический способ определения диаметра – выполнить поиск в ширину от всех вершин, тогда диаметр равен максимальному из найденных расстояний. Сложность такого подхода составляет O(mn), и в худшем случае (например, когда граф является циклом) эту оценку, по-видимому, улучшить нельзя.
Алгоритм iFUB[1] (англ. iterative Fringe Upper Bound) позволяет уменьшить количество вызовов алгоритма поиска в ширину. Для многих реальных графов будет достаточно всего нескольких вызовов и общая сложность будет близка к линейной O(m).
1.2 Математическое описание алгоритма
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
Последовательная сложность алгоритма iFUB равна O(Bm), где B – число вызовов алгоритма поиска в ширину, сложность каждого вызова O(m). В худшем случае (граф является циклом) B = n и общая сложность равна O(mn), однако для многих реальных графов B = O(1) и общая сложность составляет O(m).
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
1.9 Входные и выходные данные алгоритма
Входные данные: неориентированный граф (V, E) (n вершин v_i и m рёбер).
Объём входных данных: O(m + n).
Выходные данные: диаметр графа (V, E).
Объём выходных данных: O(1).
1.10 Свойства алгоритма
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Возможные способы и особенности параллельной реализации алгоритма
2.3 Результаты прогонов
2.4 Выводы для классов архитектур
3 Литература
- ↑ Crescenzi, Pilu, Roberto Grossi, Michel Habib, Leonardo Lanzi, and Andrea Marino. “On Computing the Diameter of Real-World Undirected Graphs.” Theoretical Computer Science 514 (November 2013): 84–95. doi:10.1016/j.tcs.2012.09.018.
