Минимальное остовное дерево Прима — это алгоритм, используемый для поиска минимального остовного дерева взвешенного неориентированного графа. Минимальное остовное дерево — это дерево, соединяющее все вершины графа с минимальным общим весом.
Вот несколько способов найти минимальное связующее дерево:
-
Алгоритм Прима: Алгоритм Прима представляет собой жадный алгоритм, который начинается с произвольной вершины и добавляет ребро минимального веса, которое соединяет текущее дерево с новой вершиной, пока не будут включены все вершины.
-
Алгоритм Краскала: Алгоритм Краскала — это еще один жадный алгоритм, который сортирует ребра графа в порядке неубывания веса и добавляет ребра одно за другим, рассматривая только те ребра, которые не образуют цикл.
-
Алгоритм Борувки. Алгоритм Борувки представляет собой алгоритм «разделяй и властвуй», который работает путем многократного поиска ребра с минимальным весом для каждого компонента графа и объединения компонентов до тех пор, пока не останется только один компонент.
-
Алгоритм обратного удаления. Алгоритм обратного удаления начинается со всех ребер графа и неоднократно удаляет ребра с наибольшим весом, которые не отключают граф, пока не останется только минимальное связующее дерево.
-
Алгоритм Ярника (также известный как алгоритм Прима-Дейкстры): Алгоритм Ярника представляет собой модификацию алгоритма Дейкстры, который находит минимальное остовное дерево, рассматривая кратчайший путь от одного источника ко всем остальным вершинам.
Алгоритм Краскала: Алгоритм Краскала — это еще один жадный алгоритм, который сортирует ребра графа в порядке неубывания веса и добавляет ребра одно за другим, рассматривая только те ребра, которые не образуют цикл.
Алгоритм Краскала. р>