Время работы алгоритма Краскала с древовидной и списочной структурой данных

Скорочена інформація про документ
dc.contributor.authorТрофимчук, А. Н.uk
dc.contributor.authorВасянин, В. А.uk
dc.contributor.authorТрофимчук, Олександр Миколайовичuk
dc.contributor.authorВасянін, Володимир Олександровичuk
dc.contributor.authorTrofimchuk, A. N.uk
dc.contributor.authorVasyanin, V. A.uk
dc.date.accessioned2015-12-07T14:17:19Zuk
dc.date.available2015-12-07T14:17:19Zuk
dc.date.issued2015uk
dc.description.abstractenUsing 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,27v², 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.uk
dc.description.abstractruПутем численных экспериментов выполнено сравнение двух реализаций алгоритма Краскала, основанных на списочной (предложенный алгоритм) и древовидной (алгоритм Тарьяна) структуре данных и алгоритма Прима. Результаты сравнения позволяют утверждать, что для решения практических задач нахождение минимального или максимального остовного дерева (леса) алгоритмы со списочной структурой данных работают не хуже, а в большинстве случаев быстрее, чем алгоритмы с древовидной структурой. Показана практическая оценка сложности предложенного алгоритма, которая для связных графов составляет O(e), где e – число ребер графа. Экспериментально доказано, что время работы алгоритма на связных разреженных графах сравнимо со временем «карманной» сортировки ребер (bucket sort). Выявлено, что предложенный алгоритм работает быстрее алгоритма Прима для графов с числом ребер не больше, чем 0,27v², где v – число вершин графа. Экспериментальное исследование алгоритма на графах, содержащих от 499500 до 71994000 ребер, показало его высокую вычислительную эффективность, и он может быть рекомендован для решения практических задач на разреженных графах или сетях большой размерности.uk
dc.description.abstractukЗа допомогою чисельних експериментів виконано порівняння двох реалізацій алгоритму Краскала, які основано на списковій (запропонований алгоритм) і деревовидній (алгоритм Тарьяна) структурах даних та алгоритму Прима. Результати порівняння дозволяють стверджувати, що для вирішення практичних задач знаходження мінімального або максимального остовного дерева (ліса) алгоритми зі списковою структурою даних працюють не гірше, а в більшості випадків швидше, ніж алгоритми з деревоподібною структурою. Показано практичну оцінку складності запропонованого алгоритму, яка для зв’язних графів складає O(e), де e – число ребер графа. Експериментально доведено, що час роботи алгоритму на зв’язних розріджених графах порівняно з часом «кишенькового» сортування ребер (bucket sort). Виявлено, що запропонований алгоритм працює швидше за алгоритм Прима для графів з кількістю ребер не більше, ніж 0,27v² де v – кількість вершин графа. Експериментальні дослідження алгоритму на графах, які містять від 499500 до 71994000 ребер, показало його високу обчислювальну ефективність і його може бути рекомендовано для вирішення практичних задач на розріджених графах або мережах великої розмірності.uk
dc.format.pagerangeС. 48–61uk
dc.identifier.citationТрофимчук, А. Н. Время работы алгоритма Краскала с древовидной и списочной структурой данных / А. Н. Трофимчук, В. А. Васянин // Системні дослідження та інформаційні технології : міжнародний науково-технічний журнал. – 2015. – № 3. – С. 48–61. – Бібліогр.: 28 назв.uk
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/14224
dc.language.isoruuk
dc.publisherПолітехнікаuk
dc.publisher.placeКиївuk
dc.source.nameСистемні дослідження та інформаційні технології : міжнародний науково-технічний журналuk
dc.status.pubpublisheduk
dc.subject.udc519.168uk
dc.titleВремя работы алгоритма Краскала с древовидной и списочной структурой данныхuk
dc.title.alternativeЧас роботи алгоритму Краскала з деревовидною та списковою структурою данихuk
dc.title.alternativeTime complexity of Kruskal’s algorithm with tree and linked list data structuresuk
dc.typeArticleuk
thesis.degree.level-uk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
GM_Trofimchuk1_Vasianin_N3_2015.pdf
Розмір:
320.57 KB
Формат:
Adobe Portable Document Format
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
1.71 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Системні дослідження та інформаційні технології: міжнародний науково-технічний журнал, № 3