Час роботи алгоритму Краскала з деревовидною та списковою структурою даних
Using numerical experiments, two implementations of Kruskal's algorithm based on the linked lists (the proposed algorithm) and tree (Tarjan's algorithm) data structures were compared with Prim's algorithm. The comparison results allow to claim that for practical problems of finding th...
Збережено в:
| Дата: | 2015 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | rus |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2015
|
| Онлайн доступ: | http://journal.iasa.kpi.ua/article/view/53409 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
Репозитарії
System research and information technologies| id |
journaliasakpiua-article-53409 |
|---|---|
| record_format |
ojs |
| institution |
System research and information technologies |
| collection |
OJS |
| language |
rus |
| format |
Article |
| author |
Trofimchuk, A. N. Vasyanin, V. A. |
| spellingShingle |
Trofimchuk, A. N. Vasyanin, V. A. Час роботи алгоритму Краскала з деревовидною та списковою структурою даних |
| author_facet |
Trofimchuk, A. N. Vasyanin, V. A. |
| author_sort |
Trofimchuk, A. N. |
| title |
Час роботи алгоритму Краскала з деревовидною та списковою структурою даних |
| title_short |
Час роботи алгоритму Краскала з деревовидною та списковою структурою даних |
| title_full |
Час роботи алгоритму Краскала з деревовидною та списковою структурою даних |
| title_fullStr |
Час роботи алгоритму Краскала з деревовидною та списковою структурою даних |
| title_full_unstemmed |
Час роботи алгоритму Краскала з деревовидною та списковою структурою даних |
| title_sort |
час роботи алгоритму краскала з деревовидною та списковою структурою даних |
| title_alt |
Time complexity of Kruskal's algorithm with tree and linked list data structures Время работы алгоритма Краскала с древовидной и списочной структурой данных |
| description |
Using numerical experiments, two implementations of Kruskal's algorithm based on the linked lists (the proposed algorithm) and tree (Tarjan's algorithm) data structures were compared with Prim's algorithm. The comparison results allow to claim that for practical problems of finding the minimum or maximum spanning trees (forest), the algorithms with linked lists data structure work no worse, and, in most cases, faster, than algorithms with the tree data structure. A practical assessment of complexity of the proposed algorithm for a connected graph was shown O(e), where e — the number of edges of the graph. It was experimentally proved that algorithm’s running time on connected sparse graphs was comparable to the time of sorting the edges of a graph by a bucket sort method. The proposed algorithm works faster than Prim's algorithm for graphs with the number of edges no more, than 0,27e2, where v is the number of vertices of the graph. The pilot study of the algorithm on the graphs containing between 499500 and 71994000 edges, showed its high computing efficiency; therefore, it can be recommended for solving practical problems on sparse graphs or networks of a big size. |
| publisher |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| publishDate |
2015 |
| url |
http://journal.iasa.kpi.ua/article/view/53409 |
| work_keys_str_mv |
AT trofimchukan timecomplexityofkruskalsalgorithmwithtreeandlinkedlistdatastructures AT vasyaninva timecomplexityofkruskalsalgorithmwithtreeandlinkedlistdatastructures AT trofimchukan vremârabotyalgoritmakraskalasdrevovidnojispisočnojstrukturojdannyh AT vasyaninva vremârabotyalgoritmakraskalasdrevovidnojispisočnojstrukturojdannyh AT trofimchukan časrobotialgoritmukraskalazderevovidnoûtaspiskovoûstrukturoûdanih AT vasyaninva časrobotialgoritmukraskalazderevovidnoûtaspiskovoûstrukturoûdanih |
| first_indexed |
2024-04-08T15:04:25Z |
| last_indexed |
2024-04-08T15:04:25Z |
| _version_ |
1795779372937904128 |
| spelling |
journaliasakpiua-article-534092016-07-21T13:43:12Z Time complexity of Kruskal's algorithm with tree and linked list data structures Время работы алгоритма Краскала с древовидной и списочной структурой данных Час роботи алгоритму Краскала з деревовидною та списковою структурою даних Trofimchuk, A. N. Vasyanin, V. A. Using numerical experiments, two implementations of Kruskal's algorithm based on the linked lists (the proposed algorithm) and tree (Tarjan's algorithm) data structures were compared with Prim's algorithm. The comparison results allow to claim that for practical problems of finding the minimum or maximum spanning trees (forest), the algorithms with linked lists data structure work no worse, and, in most cases, faster, than algorithms with the tree data structure. A practical assessment of complexity of the proposed algorithm for a connected graph was shown O(e), where e — the number of edges of the graph. It was experimentally proved that algorithm’s running time on connected sparse graphs was comparable to the time of sorting the edges of a graph by a bucket sort method. The proposed algorithm works faster than Prim's algorithm for graphs with the number of edges no more, than 0,27e2, where v is the number of vertices of the graph. The pilot study of the algorithm on the graphs containing between 499500 and 71994000 edges, showed its high computing efficiency; therefore, it can be recommended for solving practical problems on sparse graphs or networks of a big size. Путем численных экспериментов выполнено сравнение двух реализаций алгоритма Краскала, основанных на списочной (предложенный алгоритм) и древовидной (алгоритм Тарьяна) структуре данных и алгоритма Прима. Результаты сравнения позволяют утверждать, что для решения практических задач нахождение минимального или максимального остовного дерева (леса) алгоритмы со списочной структурой данных работают не хуже, а в большинстве случаев быстрее, чем алгоритмы с древовидной структурой. Показана практи-ческая оценка сложности предложенного алгоритма, которая для связных графов составляет O(e), где e — число ребер графа. Экспериментально доказано, что время работы алгоритма на связных разреженных графах сравнимо со временем "карманной" сортировки ребер (bucket sort). Выявлено, что предложенный алгоритм работает быстрее алгоритма Прима для графов с числом ребер не больше, чем 2,7e2, где e — число вершин графа. Экспериментальное исследование алгоритма на графах, содержащих от 499500 до 71994000 ребер, показало его высокую вычислительную эффективность, и он может быть рекомендован для решения практических задач на разреженных графах или сетях большой размерности. За допомогою чисельних експериментів виконано порівняння двох реалізацій алгоритму Краскала, які основано на списковій (запропонований алгоритм) і деревовидній (алгоритм Тарьяна) структурах даних та алгоритму Прима. Результати порівняння дозволяють стверджувати, що для вирішення практичних задач знаходження мінімального або максимального остовного дерева (ліса) алгоритми зі списковою структурою даних працюють не гірше, а в більшості випадків швидше, ніж алгоритми з деревоподібною структурою. Показано практичну оцінку складності запропонованого алгоритму, яка для зв’язних графів складає O(e), де e — число ребер графа. Експериментально доведено, що час роботи алгоритму на зв’язних розріджених графах порівняно з часом "кишенькового" сортування ребер (bucket sort). Виявлено, що запропонований алгоритм працює швидше за алгоритм Прима для графів з кількістю ребер не більше, ніж 0,27v2, де v — кількість вершин графа. Експериментальні дослідження алгоритму на графах, які містять від 499500 до 71994000 ребер, показало його високу обчислювальну ефективність і його може бути рекомендовано для вирішення практичних задач на розріджених графах або мережах великої розмірності. Рис.: 4. Табл.: 1. Бібліогр.: 28 назв. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2015-09-30 Article Article application/pdf http://journal.iasa.kpi.ua/article/view/53409 System research and information technologies; No. 3 (2015); 48-61 Системные исследования и информационные технологии; № 3 (2015); 48-61 Системні дослідження та інформаційні технології; № 3 (2015); 48-61 2308-8893 1681-6048 rus http://journal.iasa.kpi.ua/article/view/53409/49437 Copyright (c) 2021 System research and information technologies |