О НАХОЖДЕНИИ МИНИМАЛЬНОГО ОСТОВНОГО ДЕРЕВА

Охлупина Ольга Валентиновна, Мурашко Дмитрий Сергеевич

Использование теории графов с целью формализации и исследования данных находит широкое применение в различных отраслях человеческой деятельности, таких, как строительство, дизайн, авиация, экономика. Поиск минимального остовного дерева произвольного неориентированного взвещенного графа представляет собой широко известную задачу уже не одно десятилетие. Однако, способ решения данной задачи до сих пор не теряет своей актуальности в связи с поиском наиболее эффективной реализации. Существующие алгоритмы решения подвергаются усовершенствованию с целью универсальности использования и устойчивости к ошибкам. В работе рассмотрено решение задачи нахождения минимального остовного дерева с применением алгоритма Прима с использованием html css java script. Получен удобный инструмент для быстрого создания сетки дерева и просчёта минимального расстояния между точками с помощью выстраивания карты путей и визуально удобного отображения результата пользователю. Для удобной работы был разработан интерфейс, позволяющий манипулировать сеткой пространства

Ключевые слова:вес, вершина, граф, дерево, путь, ребро, остовное дерево, связный граф, неориентированный граф, сетка пространства