Поиск Минимального Остовного дерева

Минимальное остовное дерево

Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном взвешенном неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.

Другими словами, минимальное остовное дерево —это подграф, содержащий все вершины исходного графа, а сумма весов дуг минимальна.

Примеры использования алгоритма

Используя алгоритм поиска минимального остовного дерева, можно рассчитать минимальную стоимость прокладки дорог между городами или минимальную стоимость соединения узлов связи.

Алгоритм поиска

Для поиска мы используем Алгоритм Прима.

Как использовать

1. Создайте граф.
2. Выберите пункт меню "Алгоритмы" -> "Поиск минимального остовного дерева".