Алгоритм Прима - это алгоритм минимального остовного дерева, что принимает граф в качестве входных данных и находит подмножество ребер этого графа, который формирует дерево, включающее в себя каждую вершину, а также имеет минимальную сумму весов среди всех деревьев, которые могут быть сформированы из графа.
Как работает алгоритм Прима
Он подпадает под класс алгоритмов, называемых «жадными» алгоритмами , которые находят локальный оптимум в надежде найти глобальный оптимум.
Мы начинаем с одной вершины и продолжаем добавлять ребра с наименьшим весом, пока не достигнем нашей цели.
Шаги для реализации алгоритма Прима следующие:
- Инициализируйте минимальное остовное дерево с произвольно выбранной вершиной.
- Найдите все ребра, которые соединяют дерево с новыми вершинами, найдите минимум и добавьте его в дерево.
- Продолжайте повторять шаг 2, пока не получите минимальное остовное дерево.
Пример алгоритма Прима
Алгоритм Прима. Псевдокод.
Псевдокод для алгоритма Прима показывает, как мы создаем два набора вершин U и V-U. U содержит список вершин, которые были посещены, а V-U – список вершин, которые не были посещены. Один за другим мы перемещаем вершины из набора V-U в набор U, соединяя ребро с наименьшим весом.
Реализация алгоритма Прима в C ++
Программа ниже реализует алгоритм Прима в C ++. Несмотря на то, что используется матрица смежности для представления графа, этот алгоритм также может быть реализован с использованием списка смежности для повышения его эффективности.
#include <iostream> #include <cstring> using namespace std; #define INF 9999999 // number of vertices in grapj #define V 5 // create a 2d array of size 5x5 //for adjacency matrix to represent graph int G[V][V] = { {0, 9, 75, 0, 0}, {9, 0, 95, 19, 42}, {75, 95, 0, 51, 66}, {0, 19, 51, 0, 31}, {0, 42, 66, 31, 0} }; int main () { int no_edge; // number of edge // create a array to track selected vertex // selected will become true otherwise false int selected[V]; // set selected false initially memset (selected, false, sizeof (selected)); // set number of edge to 0 no_edge = 0; // the number of egde in minimum spanning tree will be // always less than (V -1), where V is number of vertices in //graph // choose 0th vertex and make it true selected[0] = true; int x; // row number int y; // col number // print for edge and weight cout << "Edge" << " : " << "Weight"; cout << endl; while (no_edge < V - 1) { //For every vertex in the set S, find the all adjacent vertices // , calculate the distance from the vertex selected at step 1. // if the vertex is already in the set S, discard it otherwise //choose another vertex nearest to selected vertex at step 1. int min = INF; x = 0; y = 0; for (int i = 0; i < V; i++) { if (selected[i]) { for (int j = 0; j < V; j++) { if (!selected[j] && G[i][j]) { // not in selected and there is an edge if (min > G[i][j]) { min = G[i][j]; x = i; y = j; } } } } } cout << x << " - " << y << " : " << G[x][y]; cout << endl; selected[y] = true; no_edge++; } return 0; }
Запустив приведенный выше код, мы получим вывод в виде:
Edge : Weight 0 - 1 : 9 1 - 3 : 19 3 - 4 : 31 3 - 2 : 51
Алгоритм Прима vs Краскала
Алгоритм Краскала является еще одним популярным алгоритмом минимального оставного дерева, который использует другую логику для нахождения MST графа. Вместо того, чтобы начинать с вершины, алгоритм Краскала сортирует все ребра от малого веса к большему и продолжает добавлять самые нижние ребра, игнорируя те ребра, которые создают цикл.