Время работы алгоритма Краскала с древовидной и списочной структурой данных
Путем численных экспериментов выполнено сравнение двух реализаций алгоритма Краскала, основанных на списочной (предложенный алгоритм) и древовидной (алгоритм Тарьяна) структуре данных и алгоритма Прима. Результаты сравнения позволяют утверждать, что для решения практических задач нахождение минималь...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Igor Sikorsky Kyiv Polytechnic Institute
2015-09-01
|
| Series: | Sistemnì Doslìdženâ ta Informacìjnì Tehnologìï |
| Online Access: | http://journal.iasa.kpi.ua/article/view/53409 |
| Summary: | Путем численных экспериментов выполнено сравнение двух реализаций алгоритма Краскала, основанных на списочной (предложенный алгоритм) и древовидной (алгоритм Тарьяна) структуре данных и алгоритма Прима. Результаты сравнения позволяют утверждать, что для решения практических задач нахождение минимального или максимального остовного дерева (леса) алгоритмы со списочной структурой данных работают не хуже, а в большинстве случаев быстрее, чем алгоритмы с древовидной структурой. Показана практи-ческая оценка сложности предложенного алгоритма, которая для связных графов составляет O(e), где e — число ребер графа. Экспериментально доказано, что время работы алгоритма на связных разреженных графах сравнимо со временем "карманной" сортировки ребер (bucket sort). Выявлено, что предложенный алгоритм работает быстрее алгоритма Прима для графов с числом ребер не больше, чем 2,7e2, где e — число вершин графа. Экспериментальное исследование алгоритма на графах, содержащих от 499500 до 71994000 ребер, показало его высокую вычислительную эффективность, и он может быть рекомендован для решения практических задач на разреженных графах или сетях большой размерности. |
|---|---|
| ISSN: | 1681-6048 2308-8893 |