Алгоритм Прима для мінімального остовного дерева (MST)
Знайомство з алгоритмом Прима:
Ми обговорили Алгоритм Крускала для мінімального остовного дерева . Як і алгоритм Крускала, алгоритм Прима також є a Жадібний алгоритм . Цей алгоритм завжди починається з одного вузла та переходить до кількох суміжних вузлів, щоб досліджувати всі з’єднані ребра.
Алгоритм починається з порожнього остовного дерева. Ідея полягає в підтримці двох наборів вершин. Перший набір містить вершини, які вже включені в MST, а інший набір містить вершини, які ще не включені. На кожному кроці він розглядає всі ребра, які з’єднують два набори, і вибирає ребро мінімальної ваги з цих ребер. Після вибору ребра він переміщує іншу кінцеву точку ребра до набору, що містить MST.
Група ребер, яка з’єднує два набори вершин у графі, називається скорочення в теорії графів . Отже, на кожному кроці алгоритму Прима знайдіть розріз, виберіть ребро мінімальної ваги з розрізу та включіть цю вершину в набір MST (набір, який містить уже включені вершини).
Як працює алгоритм Прима?
Роботу алгоритму Прима можна описати за допомогою наступних кроків:
Крок 1: Визначити довільну вершину як вихідну вершину МСТ.
Крок 2: Виконуйте кроки 3–5, доки не з’являться вершини, які не входять до MST (відомі як вершини смуги).
крок 3: Знайдіть ребра, що з'єднують будь-яку вершину дерева з вершинами смуги.
крок 4: Знайдіть серед цих ребер найменше.
крок 5: Додайте вибране ребро до MST, якщо воно не утворює жодного циклу.
Крок 6: Поверніть MST і вийдіть
Примітка: Для визначення циклу ми можемо розділити вершини на два набори [один набір містить вершини, включені в MST, а інший містить вершини смуг.]
Рекомендована практика Мінімальне охоплююче дерево Спробуйте!Ілюстрація алгоритму Прима:
Розглянемо наступний графік як приклад, для якого нам потрібно знайти мінімальне остовне дерево (MST).
Приклад графіка
Крок 1: По-перше, ми вибираємо довільну вершину, яка діє як початкова вершина Мінімального остовного дерева. Тут ми вибрали вершину 0 як початкову вершину.
0 обрано як початкову вершину
Крок 2: Усі ребра, що з’єднують неповну MST та інші вершини, є ребрами {0, 1} і {0, 7}. Між цими двома ребра з мінімальною вагою дорівнюють {0, 1}. Тому включіть ребро та вершину 1 у MST.
1 додається до МСТ
крок 3: Ребра, що з’єднують неповний MST з іншими вершинами, це {0, 7}, {1, 7} і {1, 2}. Серед цих ребер мінімальна вага дорівнює 8, тобто ребра {0, 7} і {1, 2}. Включимо сюди ребро {0, 7} і вершину 7 у MST. [Ми також могли б включити ребро {1, 2} і вершину 2 у MST].
7 додається в МСТ
крок 4: Ребра, які з'єднують неповний MST з вершинами смуги, це {1, 2}, {7, 6} і {7, 8}. Додайте ребро {7, 6} і вершину 6 у MST, оскільки вона має найменшу вагу (тобто 1).
6 додається в МСТ
крок 5: З’єднувальні ребра тепер такі: {7, 8}, {1, 2}, {6, 8} і {6, 5}. Включіть ребро {6, 5} і вершину 5 у MST, оскільки ребро має серед них мінімальну вагу (тобто 2).
Включіть вершину 5 у MST
Крок 6: Серед поточних сполучних ребер ребро {5, 2} має мінімальну вагу. Тож включіть це ребро та вершину 2 у MST.
Включіть вершину 2 у MST
Крок 7: Сполучними ребрами між неповним MST та іншими ребрами є {2, 8}, {2, 3}, {5, 3} та {5, 4}. Ребро з мінімальною вагою — це ребро {2, 8}, яке має вагу 2. Тому включіть це ребро та вершину 8 у MST.
Додайте вершину 8 у MST
Крок 8: Подивіться, що обидва ребра {7, 8} і {2, 3} мають однакову вагу, яка є мінімальною. Але 7 вже є частиною MST. Отже, ми розглянемо ребро {2, 3} і включимо це ребро та вершину 3 у MST.
Включіть вершину 3 у MST
Крок 9: Залишається включити лише вершину 4. Мінімальне зважене ребро від неповного MST до 4 становить {3, 4}.
Включіть вершину 4 у MST
Остаточна структура MST така, а вага ребер MST дорівнює (4 + 8 + 1 + 2 + 4 + 2 + 7 + 9) = 37 .
Структура MST сформована за допомогою описаного вище методу
Примітка: Якби ми вибрали ребро {1, 2} на третьому кроці, MST виглядав би так.
Структура альтернативного MST, якщо ми вибрали ребро {1, 2} у MST
Як реалізувати алгоритм Прима?
Виконайте наведені кроки, щоб використовувати Алгоритм Прима згадане вище для знаходження MST графа:
- Створіть набір mstSet який відстежує вершини, які вже включені в MST.
- Призначте значення ключа всім вершинам у вхідному графі. Ініціалізуйте всі ключові значення як НЕСКІНЧЕННІ. Призначте ключове значення 0 для першої вершини, щоб вона вибиралася першою.
- Поки mstSet не включає всі вершини
- Виберіть вершину в цього немає в mstSet і має мінімальне значення ключа.
- Включати в в mstSet .
- Оновіть значення ключа всіх суміжних вершин в . Щоб оновити ключові значення, пройдіть по всіх суміжних вершинах.
- Для кожної сусідньої вершини в , якщо вага краю u-v менше попереднього значення ключа в оновіть значення ключа як вагу u-v .
Ідея використання ключових значень полягає у виборі мінімального вагового краю з вирізати . Значення ключа використовуються тільки для вершин, які ще не включені в MST, значення ключа для цих вершин вказує на мінімальну вагу ребер, що з’єднують їх з набором вершин, включених в MST.
Нижче наведено реалізацію підходу:
C++
// A C++ program for Prim's Minimum> // Spanning Tree (MST) algorithm. The program is> // for adjacency matrix representation of the graph> #include> using> namespace> std;> // Number of vertices in the graph> #define V 5> // A utility function to find the vertex with> // minimum key value, from the set of vertices> // not yet included in MST> int> minKey(> int> key[],> bool> mstSet[])> {> > // Initialize min value> > int> min = INT_MAX, min_index;> > for> (> int> v = 0; v if (mstSet[v] == false && key[v] min = key[v], min_index = v; return min_index; } // A utility function to print the // constructed MST stored in parent[] void printMST(int parent[], int graph[V][V]) { cout < < 'Edge Weight
'; for (int i = 1; i cout < < parent[i] < < ' - ' < < i < < ' ' < < graph[i][parent[i]] < < '
'; } // Function to construct and print MST for // a graph represented using adjacency // matrix representation void primMST(int graph[V][V]) { // Array to store constructed MST int parent[V]; // Key values used to pick minimum weight edge in cut int key[V]; // To represent set of vertices included in MST bool mstSet[V]; // Initialize all keys as INFINITE for (int i = 0; i key[i] = INT_MAX, mstSet[i] = false; // Always include first 1st vertex in MST. // Make key 0 so that this vertex is picked as first // vertex. key[0] = 0; // First node is always root of MST parent[0] = -1; // The MST will have V vertices for (int count = 0; count // Pick the minimum key vertex from the // set of vertices not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of // the adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (int v = 0; v // graph[u][v] is non zero only for adjacent // vertices of m mstSet[v] is false for vertices // not yet included in MST Update the key only // if graph[u][v] is smaller than key[v] if (graph[u][v] && mstSet[v] == false && graph[u][v] parent[v] = u, key[v] = graph[u][v]; } // Print the constructed MST printMST(parent, graph); } // Driver's code int main() { int graph[V][V] = { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution primMST(graph); return 0; } // This code is contributed by rathbhupendra> |
C
// A C program for Prim's Minimum> // Spanning Tree (MST) algorithm. The program is> // for adjacency matrix representation of the graph> #include> #include> #include> // Number of vertices in the graph> #define V 5> // A utility function to find the vertex with> // minimum key value, from the set of vertices> // not yet included in MST> int> minKey(> int> key[],> bool> mstSet[])> {> > // Initialize min value> > int> min = INT_MAX, min_index;> > for> (> int> v = 0; v if (mstSet[v] == false && key[v] min = key[v], min_index = v; return min_index; } // A utility function to print the // constructed MST stored in parent[] int printMST(int parent[], int graph[V][V]) { printf('Edge Weight
'); for (int i = 1; i printf('%d - %d %d
', parent[i], i, graph[i][parent[i]]); } // Function to construct and print MST for // a graph represented using adjacency // matrix representation void primMST(int graph[V][V]) { // Array to store constructed MST int parent[V]; // Key values used to pick minimum weight edge in cut int key[V]; // To represent set of vertices included in MST bool mstSet[V]; // Initialize all keys as INFINITE for (int i = 0; i key[i] = INT_MAX, mstSet[i] = false; // Always include first 1st vertex in MST. // Make key 0 so that this vertex is picked as first // vertex. key[0] = 0; // First node is always root of MST parent[0] = -1; // The MST will have V vertices for (int count = 0; count // Pick the minimum key vertex from the // set of vertices not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of // the adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (int v = 0; v // graph[u][v] is non zero only for adjacent // vertices of m mstSet[v] is false for vertices // not yet included in MST Update the key only // if graph[u][v] is smaller than key[v] if (graph[u][v] && mstSet[v] == false && graph[u][v] parent[v] = u, key[v] = graph[u][v]; } // print the constructed MST printMST(parent, graph); } // Driver's code int main() { int graph[V][V] = { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution primMST(graph); return 0; }> |
Java
// A Java program for Prim's Minimum Spanning Tree (MST)> // algorithm. The program is for adjacency matrix> // representation of the graph> import> java.io.*;> import> java.lang.*;> import> java.util.*;> class> MST {> > // Number of vertices in the graph> > private> static> final> int> V => 5> ;> > // A utility function to find the vertex with minimum> > // key value, from the set of vertices not yet included> > // in MST> > int> minKey(> int> key[], Boolean mstSet[])> > {> > // Initialize min value> > int> min = Integer.MAX_VALUE, min_index = -> 1> ;> > for> (> int> v => 0> ; v if (mstSet[v] == false && key[v] min = key[v]; min_index = v; } return min_index; } // A utility function to print the constructed MST // stored in parent[] void printMST(int parent[], int graph[][]) { System.out.println('Edge Weight'); for (int i = 1; i System.out.println(parent[i] + ' - ' + i + ' ' + graph[i][parent[i]]); } // Function to construct and print MST for a graph // represented using adjacency matrix representation void primMST(int graph[][]) { // Array to store constructed MST int parent[] = new int[V]; // Key values used to pick minimum weight edge in // cut int key[] = new int[V]; // To represent set of vertices included in MST Boolean mstSet[] = new Boolean[V]; // Initialize all keys as INFINITE for (int i = 0; i key[i] = Integer.MAX_VALUE; mstSet[i] = false; } // Always include first 1st vertex in MST. // Make key 0 so that this vertex is // picked as first vertex key[0] = 0; // First node is always root of MST parent[0] = -1; // The MST will have V vertices for (int count = 0; count 1; count++) { // Pick the minimum key vertex from the set of // vertices not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of the // adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (int v = 0; v // graph[u][v] is non zero only for adjacent // vertices of m mstSet[v] is false for // vertices not yet included in MST Update // the key only if graph[u][v] is smaller // than key[v] if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] parent[v] = u; key[v] = graph[u][v]; } } // Print the constructed MST printMST(parent, graph); } public static void main(String[] args) { MST t = new MST(); int graph[][] = new int[][] { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution t.primMST(graph); } } // This code is contributed by Aakash Hasija> |
Python3
# A Python3 program for> # Prim's Minimum Spanning Tree (MST) algorithm.> # The program is for adjacency matrix> # representation of the graph> # Library for INT_MAX> import> sys> class> Graph():> > def> __init__(> self> , vertices):> > self> .V> => vertices> > self> .graph> => [[> 0> for> column> in> range> (vertices)]> > for> row> in> range> (vertices)]> > # A utility function to print> > # the constructed MST stored in parent[]> > def> printMST(> self> , parent):> > print> (> 'Edge Weight'> )> > for> i> in> range> (> 1> ,> self> .V):> > print> (parent[i],> '-'> , i,> ' '> ,> self> .graph[i][parent[i]])> > # A utility function to find the vertex with> > # minimum distance value, from the set of vertices> > # not yet included in shortest path tree> > def> minKey(> self> , key, mstSet):> > # Initialize min value> > min> => sys.maxsize> > for> v> in> range> (> self> .V):> > if> key[v] <> min> and> mstSet[v]> => => False> :> > min> => key[v]> > min_index> => v> > return> min_index> > # Function to construct and print MST for a graph> > # represented using adjacency matrix representation> > def> primMST(> self> ):> > # Key values used to pick minimum weight edge in cut> > key> => [sys.maxsize]> *> self> .V> > parent> => [> None> ]> *> self> .V> # Array to store constructed MST> > # Make key 0 so that this vertex is picked as first vertex> > key[> 0> ]> => 0> > mstSet> => [> False> ]> *> self> .V> > parent[> 0> ]> => -> 1> # First node is always the root of> > for> cout> in> range> (> self> .V):> > # Pick the minimum distance vertex from> > # the set of vertices not yet processed.> > # u is always equal to src in first iteration> > u> => self> .minKey(key, mstSet)> > # Put the minimum distance vertex in> > # the shortest path tree> > mstSet[u]> => True> > # Update dist value of the adjacent vertices> > # of the picked vertex only if the current> > # distance is greater than new distance and> > # the vertex in not in the shortest path tree> > for> v> in> range> (> self> .V):> > # graph[u][v] is non zero only for adjacent vertices of m> > # mstSet[v] is false for vertices not yet included in MST> > # Update the key only if graph[u][v] is smaller than key[v]> > if> self> .graph[u][v]>> 0> and> mstSet[v]> => => False> > > and> key[v]>> self> .graph[u][v]:> > key[v]> => self> .graph[u][v]> > parent[v]> => u> > self> .printMST(parent)> # Driver's code> if> __name__> => => '__main__'> :> > g> => Graph(> 5> )> > g.graph> => [[> 0> ,> 2> ,> 0> ,> 6> ,> 0> ],> > [> 2> ,> 0> ,> 3> ,> 8> ,> 5> ],> > [> 0> ,> 3> ,> 0> ,> 0> ,> 7> ],> > [> 6> ,> 8> ,> 0> ,> 0> ,> 9> ],> > [> 0> ,> 5> ,> 7> ,> 9> ,> 0> ]]> > g.primMST()> # Contributed by Divyanshu Mehta> |
C#
// A C# program for Prim's Minimum> // Spanning Tree (MST) algorithm.> // The program is for adjacency> // matrix representation of the graph> using> System;> class> MST {> > // Number of vertices in the graph> > static> int> V = 5;> > // A utility function to find> > // the vertex with minimum key> > // value, from the set of vertices> > // not yet included in MST> > static> int> minKey(> int> [] key,> bool> [] mstSet)> > {> > // Initialize min value> > int> min => int> .MaxValue, min_index = -1;> > for> (> int> v = 0; v if (mstSet[v] == false && key[v] min = key[v]; min_index = v; } return min_index; } // A utility function to print // the constructed MST stored in parent[] static void printMST(int[] parent, int[, ] graph) { Console.WriteLine('Edge Weight'); for (int i = 1; i Console.WriteLine(parent[i] + ' - ' + i + ' ' + graph[i, parent[i]]); } // Function to construct and // print MST for a graph represented // using adjacency matrix representation static void primMST(int[, ] graph) { // Array to store constructed MST int[] parent = new int[V]; // Key values used to pick // minimum weight edge in cut int[] key = new int[V]; // To represent set of vertices // included in MST bool[] mstSet = new bool[V]; // Initialize all keys // as INFINITE for (int i = 0; i key[i] = int.MaxValue; mstSet[i] = false; } // Always include first 1st vertex in MST. // Make key 0 so that this vertex is // picked as first vertex // First node is always root of MST key[0] = 0; parent[0] = -1; // The MST will have V vertices for (int count = 0; count // Pick the minimum key vertex // from the set of vertices // not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex // to the MST Set mstSet[u] = true; // Update key value and parent // index of the adjacent vertices // of the picked vertex. Consider // only those vertices which are // not yet included in MST for (int v = 0; v // graph[u][v] is non zero only // for adjacent vertices of m // mstSet[v] is false for vertices // not yet included in MST Update // the key only if graph[u][v] is // smaller than key[v] if (graph[u, v] != 0 && mstSet[v] == false && graph[u, v] parent[v] = u; key[v] = graph[u, v]; } } // Print the constructed MST printMST(parent, graph); } // Driver's Code public static void Main() { int[, ] graph = new int[, ] { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution primMST(graph); } } // This code is contributed by anuj_67.> |
Javascript
> // Number of vertices in the graph> let V = 5;> // A utility function to find the vertex with> // minimum key value, from the set of vertices> // not yet included in MST> function> minKey(key, mstSet)> {> > // Initialize min value> > let min = Number.MAX_VALUE, min_index;> > for> (let v = 0; v if (mstSet[v] == false && key[v] min = key[v], min_index = v; return min_index; } // A utility function to print the // constructed MST stored in parent[] function printMST(parent, graph) { document.write('Edge Weight' + ' '); for (let i = 1; i document.write(parent[i] + ' - ' + i + ' ' + graph[i][parent[i]] + ' '); } // Function to construct and print MST for // a graph represented using adjacency // matrix representation function primMST(graph) { // Array to store constructed MST let parent = []; // Key values used to pick minimum weight edge in cut let key = []; // To represent set of vertices included in MST let mstSet = []; // Initialize all keys as INFINITE for (let i = 0; i key[i] = Number.MAX_VALUE, mstSet[i] = false; // Always include first 1st vertex in MST. // Make key 0 so that this vertex is picked as first vertex. key[0] = 0; parent[0] = -1; // First node is always root of MST // The MST will have V vertices for (let count = 0; count { // Pick the minimum key vertex from the // set of vertices not yet included in MST let u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of // the adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (let v = 0; v // graph[u][v] is non zero only for adjacent vertices of m // mstSet[v] is false for vertices not yet included in MST // Update the key only if graph[u][v] is smaller than key[v] if (graph[u][v] && mstSet[v] == false && graph[u][v] parent[v] = u, key[v] = graph[u][v]; } // print the constructed MST printMST(parent, graph); } // Driver code let graph = [ [ 0, 2, 0, 6, 0 ], [ 2, 0, 3, 8, 5 ], [ 0, 3, 0, 0, 7 ], [ 6, 8, 0, 0, 9 ], [ 0, 5, 7, 9, 0 ] ]; // Print the solution primMST(graph); // This code is contributed by Dharanendra L V.> |
Вихід
Edge Weight 0 - 1 2 1 - 2 3 0 - 3 6 1 - 4 5
Аналіз складності алгоритму Прима:
Часова складність: O(V 2 ), якщо вхід граф представлений за допомогою списку суміжності , то часова складність алгоритму Прима може бути зменшена до O(E * logV) за допомогою двійкової купи. У цій реалізації ми завжди вважаємо, що остовне дерево починається з кореня графа
Допоміжний простір: O(V)
Інші реалізації алгоритму Прима:
Нижче наведено деякі інші реалізації алгоритму Прима
- Алгоритм Прима для подання матриці суміжності – У цій статті ми обговорили метод реалізації алгоритму Прима, якщо граф представлений матрицею суміжності.
- Алгоритм Прима для подання списку суміжності – У цій статті описується реалізація алгоритму Prim для графів, представлених списком суміжності.
- Алгоритм Прима з використанням пріоритетної черги: У цій статті ми обговорили економічний підхід до впровадження алгоритму Прима.
ОПТИМІЗОВАНИЙ ПІДХІД АЛГОРИТМУ ПРИМА:
інтуїція
- Ми перетворюємо матрицю суміжності в список суміжності за допомогою ArrayList
. - Потім ми створюємо клас Pair для зберігання вершини та її ваги.
- Ми сортуємо список за найменшою вагою.
- Ми створюємо пріоритетну чергу і вставляємо першу вершину та її вагу в чергу
- Тоді ми просто переходимо через його краї та зберігаємо найменшу вагу в змінній, що називається років.
- Нарешті після всіх вершин ми повертаємо ans.
Реалізація
C++
#include> using> namespace> std;> typedef> pair <> int> ,> int> >pii;> // Function to find sum of weights of edges of the Minimum Spanning Tree.> int> spanningTree(> int> V,> int> E,> int> edges[][3])> {> > // Create an adjacency list representation of the graph> > vectorint>> adj[V]; // Заповнити список суміжності ребрами та їх вагами для (int i = 0; i int u = edges[i][0]; int v = edges[i][1]; int wt = edges[i][2) ]; adj[u].push_back({v, wt});adj[v].push_back({u,wt}); // Створення черги пріоритетів з їх вагами priority_queue pq; відвіданий масив для відстеження вектора відвіданих вершин |
Java
// A Java program for Prim's Minimum Spanning Tree (MST)> // algorithm. The program is for adjacency list> // representation of the graph> import> java.io.*;> import> java.util.*;> // Class to form pair> class> Pair> implements> Comparable> {> > int> v;> > int> wt;> > Pair(> int> v,> int> wt)> > {> > this> .v=v;> > this> .wt=wt;> > }> > public> int> compareTo(Pair that)> > {> > return> this> .wt-that.wt;> > }> }> class> GFG {> // Function of spanning tree> static> int> spanningTree(> int> V,> int> E,> int> edges[][])> > {> > ArrayList adj=> new> ArrayList();> > for> (> int> i=> 0> ;i { adj.add(new ArrayList()); } for(int i=0;i { int u=edges[i][0]; int v=edges[i][1]; int wt=edges[i][2]; adj.get(u).add(new Pair(v,wt)); adj.get(v).add(new Pair(u,wt)); } PriorityQueue pq = new PriorityQueue(); pq.add(new Pair(0,0)); int[] vis=new int[V]; int s=0; while(!pq.isEmpty()) { Pair node=pq.poll(); int v=node.v; int wt=node.wt; if(vis[v]==1) continue; s+=wt; vis[v]=1; for(Pair it:adj.get(v)) { if(vis[it.v]==0) { pq.add(new Pair(it.v,it.wt)); } } } return s; } // Driver code public static void main (String[] args) { int graph[][] = new int[][] {{0,1,5}, {1,2,3}, {0,2,1}}; // Function call System.out.println(spanningTree(3,3,graph)); } }> |
Python3
import> heapq> def> tree(V, E, edges):> > # Create an adjacency list representation of the graph> > adj> => [[]> for> _> in> range> (V)]> > # Fill the adjacency list with edges and their weights> > for> i> in> range> (E):> > u, v, wt> => edges[i]> > adj[u].append((v, wt))> > adj[v].append((u, wt))> > # Create a priority queue to store edges with their weights> > pq> => []> > # Create a visited array to keep track of visited vertices> > visited> => [> False> ]> *> V> > # Variable to store the result (sum of edge weights)> > res> => 0> > # Start with vertex 0> > heapq.heappush(pq, (> 0> ,> 0> ))> > # Perform Prim's algorithm to find the Minimum Spanning Tree> > while> pq:> > wt, u> => heapq.heappop(pq)> > if> visited[u]:> > continue> > # Skip if the vertex is already visited> > res> +> => wt> > # Add the edge weight to the result> > visited[u]> => True> > # Mark the vertex as visited> > # Explore the adjacent vertices> > for> v, weight> in> adj[u]:> > if> not> visited[v]:> > heapq.heappush(pq, (weight, v))> > # Add the adjacent edge to the priority queue> > return> res> > # Return the sum of edge weights of the Minimum Spanning Tree> if> __name__> => => '__main__'> :> > graph> => [[> 0> ,> 1> ,> 5> ],> > [> 1> ,> 2> ,> 3> ],> > [> 0> ,> 2> ,> 1> ]]> > # Function call> > print> (tree(> 3> ,> 3> , graph))> |
C#
using> System;> using> System.Collections.Generic;> public> class> MinimumSpanningTree> {> > // Function to find sum of weights of edges of the Minimum Spanning Tree.> > public> static> int> SpanningTree(> int> V,> int> E,> int> [,] edges)> > {> > // Create an adjacency list representation of the graph> > Listint[]>> adj = новий Listint[]>>(); for (int i = 0; i { adj.Add(новий список |
Javascript
class PriorityQueue {> > constructor() {> > this> .heap = [];> > }> > enqueue(value) {> > this> .heap.push(value);> > let i => this> .heap.length - 1;> > while> (i>0) {> > let j = Math.floor((i - 1) / 2);> > if> (> this> .heap[i][0]>=> this> .heap[j][0]) {> > break> ;> > }> > [> this> .heap[i],> this> .heap[j]] = [> this> .heap[j],> this> .heap[i]];> > i = j;> > }> > }> > dequeue() {> > if> (> this> .heap.length === 0) {> > throw> new> Error(> 'Queue is empty'> );> > }> > let i => this> .heap.length - 1;> > const result => this> .heap[0];> > this> .heap[0] => this> .heap[i];> > this> .heap.pop();> > i--;> > let j = 0;> > while> (> true> ) {> > const left = j * 2 + 1;> > if> (left>i) {> > break> ;> > }> > const right = left + 1;> > let k = left;> > if> (right <= i &&> this> .heap[right][0] <> this> .heap[left][0]) {> > k = right;> > }> > if> (> this> .heap[j][0] <=> this> .heap[k][0]) {> > break> ;> > }> > [> this> .heap[j],> this> .heap[k]] = [> this> .heap[k],> this> .heap[j]];> > j = k;> > }> > return> result;> > }> > get count() {> > return> this> .heap.length;> > }> }> function> spanningTree(V, E, edges) {> > // Create an adjacency list representation of the graph> > const adj => new> Array(V).fill(> null> ).map(() =>[]);>> > // Fill the adjacency list with edges and their weights> > for> (let i = 0; i const [u, v, wt] = edges[i]; adj[u].push([v, wt]); adj[v].push([u, wt]); } // Create a priority queue to store edges with their weights const pq = new PriorityQueue(); // Create a visited array to keep track of visited vertices const visited = new Array(V).fill(false); // Variable to store the result (sum of edge weights) let res = 0; // Start with vertex 0 pq.enqueue([0, 0]); // Perform Prim's algorithm to find the Minimum Spanning Tree while (pq.count>0) { const p = pq.dequeue(); const wt = p[0]; // Вага ребра const u = p[1]; // Вершина, з'єднана з ребром if (visited[u]) { continue; // Пропустити, якщо вершину вже відвідали } res += wt; // Додайте вагу краю до результату visited[u] = true; // Позначити вершину як відвідану // Дослідити суміжні вершини для (const v of adj[u]) { // v[0] представляє вершину, а v[1] представляє вагу ребра if (!visited[v[0) ]]) { pq.enqueue([v[1], v[0]]); // Додати сусіднє ребро до черги пріоритетів } } } return res; // Повертає суму ваг ребер мінімального остовного дерева } // Приклад використання const graph = [[0, 1, 5], [1, 2, 3], [0, 2, 1]]; // Виклик функції console.log(spanningTree(3, 3, graph));> |
Вихід
4
Аналіз складності алгоритму Прима:
Часова складність: O(E*log(E)), де E – кількість ребер
Допоміжний простір: O(V^2), де V - номер вершини
Алгоритм Прима для знаходження мінімального остовного дерева (MST):
Переваги:
- Алгоритм Прима гарантовано знаходить MST у зв’язаному зваженому графі.
- Він має часову складність O(E log V) з використанням бінарної купи або купи Фібоначчі, де E — кількість ребер, а V — кількість вершин.
- Це відносно простий алгоритм для розуміння та реалізації порівняно з деякими іншими алгоритмами MST.
Недоліки:
- Подібно до алгоритму Крускала, алгоритм Прима може працювати повільно на щільних графах із багатьма ребрами, оскільки вимагає повторення всіх ребер принаймні один раз.
- Алгоритм Prim покладається на пріоритетну чергу, яка може займати додаткову пам’ять і сповільнювати роботу алгоритму на дуже великих графіках.
- Вибір початкового вузла може вплинути на вихід MST, що може бути небажаним у деяких програмах.
