Метод Прима для построения МОД в связном графе
ДОБАВИТЬ В КОНСПЕКТ
НАВИГАЦИЯ ПО СТРАНИЦЕ
Метод Прима:
На вход алгоритма подаётся связный неориентированный граф. Для каждого ребра задаётся его стоимость.
Сначала берётся произвольная вершина и находится ребро, инцидентное данной вершине и обладающее наименьшей стоимостью. Найденное ребро и соединяемые им две вершины образуют дерево. Затем, рассматриваются рёбра графа, один конец которых — уже принадлежащая дереву вершина, а другой — нет; из этих рёбер выбирается ребро наименьшей стоимости. Выбираемое на каждом шаге ребро присоединяется к дереву. Рост дерева происходит до тех пор, пока не будут исчерпаны все вершины исходного графа.
Результатом работы алгоритма является остовное дерево минимальной стоимости.
Полезные ссылки:
