Определение диаметра графа: различия между версиями
| [непроверенная версия] | [досмотренная версия] |
Daryin (обсуждение | вклад) (Общее описание алгоритма) |
ASA (обсуждение | вклад) |
||
| (не показаны 4 промежуточные версии 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 Общее описание алгоритма
Диаметром неориентированного графа называется максимальная длина кратчайшего пути между двумя вершинами. Классический способ определения диаметра – выполнить поиск в ширину от всех вершин, тогда диаметр равен максимальному из найденных расстояний. Сложность такого подхода составляет [math]O(mn)[/math], и в худшем случае (например, когда граф является циклом) эту оценку, по-видимому, улучшить нельзя.
Алгоритм iFUB[1] (англ. iterative Fringe 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].
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.
