Алгоритм Прима

Содержание

Как работает алгоритм Прима
Пример алгоритма Прима
Псевдокод алгоритма Прима
Примеры Python, Java и C / C ++
Алгоритм Прима против Крускала
Сложность алгоритма Прима
Применение алгоритма Прима

В этом руководстве вы узнаете, как работает алгоритм Прима. Также вы найдете рабочие примеры алгоритма Прима на языках C, C ++, Java и Python.

Алгоритм Прима - это алгоритм минимального остовного дерева, который принимает граф в качестве входных данных и находит подмножество ребер этого графа, которые

сформировать дерево, включающее каждую вершину
имеет минимальную сумму весов среди всех деревьев, которые могут быть сформированы из графа

Как работает алгоритм Прима

Он подпадает под класс алгоритмов, называемых жадными алгоритмами, которые находят локальный оптимум в надежде найти глобальный оптимум.

Мы начинаем с одной вершины и продолжаем добавлять ребра с наименьшим весом, пока не достигнем нашей цели.

Шаги по реализации алгоритма Прима следующие:

Инициализировать минимальное остовное дерево вершиной, выбранной случайным образом.
Найдите все ребра, которые соединяют дерево с новыми вершинами, найдите минимум и добавьте его в дерево
Продолжайте повторять шаг 2, пока не получите минимальное остовное дерево.

Пример алгоритма Прима

Начните с взвешенным графом

Выберите вершину

Выберите самый короткий край от этой вершины и добавить его

выбрать ближайшую вершину еще не в решении

Выберите ближайший край еще не в растворе, если есть несколько вариантов, выбрать один в произвольном порядке

Повторяйте , пока иметь остовное дерево

Псевдокод алгоритма Прима

Псевдокод алгоритма prim показывает, как мы создаем два набора вершин U и VU. U содержит список вершин, которые были посещены, а VU - список вершин, которые не были посещены. Одна за другой мы перемещаем вершины из множества VU в множество U, соединяя ребро наименьшего веса.

 T = ∅; U = ( 1 ); while (U ≠ V) let (u, v) be the lowest cost edge such that u ∈ U and v ∈ V - U; T = T ∪ ((u, v)) U = U ∪ (v)

Примеры Python, Java и C / C ++

Хотя используется матричное представление графов, этот алгоритм также может быть реализован с использованием списка смежности для повышения его эффективности.

Python Java C C ++

 # Prim's Algorithm in Python INF = 9999999 # number of vertices in graph V = 5 # create a 2d array of size 5x5 # for adjacency matrix to represent graph G = ((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)) # create a array to track selected vertex # selected will become true otherwise false selected = (0, 0, 0, 0, 0) # 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 # print for edge and weight print("Edge : Weight") while (no_edge  G(i)(j): minimum = G(i)(j) x = i y = j print(str(x) + "-" + str(y) + ":" + str(G(x)(y))) selected(y) = True no_edge += 1

 // Prim's Algorithm in Java import java.util.Arrays; class PGraph ( public void Prim(int G()(), int V) ( int INF = 9999999; int no_edge; // number of edge // create a array to track selected vertex // selected will become true otherwise false boolean() selected = new boolean(V); // set selected false initially Arrays.fill(selected, false); // 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; // print for edge and weight System.out.println("Edge : Weight"); 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; int x = 0; // row number int y = 0; // col number for (int i = 0; i < V; i++) ( if (selected(i) == true) ( for (int j = 0; j G(i)(j)) ( min = G(i)(j); x = i; y = j; ) ) ) ) ) System.out.println(x + " - " + y + " : " + G(x)(y)); selected(y) = true; no_edge++; ) ) public static void main(String() args) ( PGraph g = new PGraph(); // number of vertices in grapj int V = 5; // create a 2d array of size 5x5 // for adjacency matrix to represent graph int()() G = ( ( 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 ) ); g.Prim(G, V); ) )

 // Prim's Algorithm in C #include #include #define INF 9999999 // number of vertices in graph #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 printf("Edge : Weight"); 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 G(i)(j)) ( min = G(i)(j); x = i; y = j; ) ) ) ) ) printf("%d - %d : %d", x, y, G(x)(y)); selected(y) = true; no_edge++; ) return 0; )

 // Prim's Algorithm in C++ #include #include 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 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; )

Алгоритм Прима против Крускала

Алгоритм Крускала - еще один популярный алгоритм минимального остовного дерева, который использует другую логику для поиска MST графа. Вместо того, чтобы начинать с вершины, алгоритм Краскала сортирует все ребра от низкого веса к высокому и продолжает добавлять самые низкие ребра, игнорируя те ребра, которые создают цикл.