Применение алгоритмов Kruskal и Prim

Ответ 1

Вначале были изучены минимальные связующие деревья для способов выведения электрических сетей таким образом, чтобы минимизировать общую стоимость проводки. В минимальном остовном дереве все узлы (дома) будут соединены с электропитанием проводами, которые имеют минимальную стоимость и избыточность (разрезание любого провода обязательно разрезает силовую сетку на две части).

С тех пор проблема хорошо изучена и часто используется в качестве подпрограммы в более сложных алгоритмах. алгоритм Christofides для поиска приближенных решений проблемы Traveling Salesman использует его на ключевом этапе, как и некоторые алгоритмы поиска деревьев Штейнера.

Минимальные связующие деревья также использовались для генерации лабиринтов. Оба алгоритма Kruskal и Prim были использованы таким образом, часто создавая высококачественные лабиринты.

Если вам интересна полная история минимальной проблемы связующего дерева, ее приложений и ее алгоритмов, есть действительно превосходная бумага доступная здесь, который охватывает все эти. Я настоятельно рекомендую дать ему прочитать!

Надеюсь, это поможет!

Ответ 2

Цитата из Википедии:

Одним из примеров могла бы стать компания кабельного телевидения, прокладывающая кабель в новый район. Если он ограничен, чтобы закопать кабель только по определенным путям, тогда будет график, который указывает, какие точки связаны этими путями. Некоторые из этих путей могут быть более дорогими, потому что они длиннее или требуют, чтобы кабель был похоронен глубже; эти пути будут представлены ребрами с более крупными весами. Связующее дерево для этого графа будет подмножеством тех путей, которые не имеют циклов, но все же соединяются с каждым домом. Возможно, существует несколько связующих деревьев. Минимальное связующее дерево будет иметь наименьшую общую стоимость.

Источник: http://en.wikipedia.org/wiki/Minimum_spanning_tree

Ответ 3

Сначала вы должны понимать, что алгоритм Prim и Kruskal полезен для нахождения минимального остовного дерева на графике. Одно из практических применений минимального остовного дерева, я могу думать о том, что соединяет разные офисы той же компании с наименьшими затратами.

Ответ 4

• Топология
• Картография
• Геометрия
• Кластеризация
• Алгоритмы маршрутизации
• Поколение лабиринтов
• Механические/Электрические/Компьютерные сети
• Исследование молекулярных связей в химии

Ответ 5

Приложения алгоритмов Kruskal и Prim часто возникают в компьютерных сетях. Например, если у вас большая сеть с множеством коммутаторов, поиск минимального связующего дерева будет жизненно важен для обеспечения того, чтобы только минимальное количество пакетов было передано по сети.