У цій статті ми обговоримо алгоритм прим. Разом з алгоритмом ми також побачимо складність, роботу, приклад і реалізацію алгоритму Prim.

Перш ніж розпочати основну тему, ми повинні обговорити основні та важливі терміни, такі як охоплююче дерево та мінімальне остовне дерево.

Остовне дерево - Остовне дерево — це підграф неорієнтованого зв’язного графа.

Мінімальне охоплююче дерево - Мінімальне остовне дерево можна визначити як остовне дерево, в якому сума ваг ребра мінімальна. Вага остовного дерева - це сума ваг, наданих ребрам остовного дерева.

Тепер давайте почнемо основну тему.

Алгоритм Прима це жадібний алгоритм, який використовується для знаходження мінімального остовного дерева з графа. Алгоритм Прима знаходить підмножину ребер, яка включає кожну вершину графа, так що суму ваг ребер можна мінімізувати.

Алгоритм Прима починається з одного вузла та досліджує всі суміжні вузли з усіма сполучними ребрами на кожному кроці. Вибрано ребра з мінімальними вагами, які не викликають циклів у графі.

Як працює алгоритм прима?

Алгоритм Прима — це жадібний алгоритм, який починається з однієї вершини та продовжує додавати ребра з найменшою вагою, доки не буде досягнуто мети. Кроки для реалізації алгоритму прима наведені нижче:

• По-перше, ми повинні ініціалізувати MST з випадково вибраною вершиною.
• Тепер ми маємо знайти всі ребра, які з’єднують дерево в описаному вище кроці з новими вершинами. Серед знайдених ребер виберіть мінімальне ребро та додайте його до дерева.
• Повторюйте крок 2, доки не буде сформовано мінімальне остовне дерево.

Застосування алгоритму прима:

• Алгоритм Прима можна використовувати при проектуванні мережі.
• Його можна використовувати для створення мережевих циклів.
• Також його можна використовувати для прокладки електропроводки.

Приклад алгоритму прима

Тепер давайте подивимося на прикладі роботи алгоритму прима. На прикладі буде простіше зрозуміти алгоритм прима.

Припустимо, зважений графік -

Крок 1 - Спочатку ми повинні вибрати вершину з наведеного вище графа. Давайте виберемо Б.

об'єкт для jsonobject java

Крок 2 - Тепер нам потрібно вибрати та додати найкоротше ребро з вершини B. Є два ребра з вершини B, які від B до C з вагою 10 і ребро B до D з вагою 4. Серед ребер ребро BD має мінімальну вагу . Отже, додайте його до MST.

Крок 3 - Тепер знову виберіть ребро з мінімальною вагою серед усіх інших ребер. У цьому випадку такими ребрами є ребра DE і CD. Додайте їх до MST і вивчіть межі C, тобто E і A. Отже, виберіть ребро DE і додайте його до MST.

Крок 4 - Тепер виберіть крайовий компакт-диск і додайте його до MST.

Крок 5 - Тепер виберіть край CA. Тут ми не можемо вибрати ребро CE, оскільки це створить цикл на графі. Отже, виберіть крайовий CA та додайте його до MST.

Отже, граф, створений на кроці 5, є мінімальним остовним деревом заданого графа. Вартість MST наведена нижче -

Вартість МСТ = 4 + 2 + 1 + 3 = 10 од.

Алгоритм

 Step 1: Select a starting vertex Step 2: Repeat Steps 3 and 4 until there are fringe vertices Step 3: Select an edge 'e' connecting the tree vertex and fringe vertex that has minimum weight Step 4: Add the selected edge and the vertex to the minimum spanning tree T [END OF LOOP] Step 5: EXIT 

Складність алгоритму Прима

Тепер давайте подивимося на часову складність алгоритму Прима. Час роботи алгоритму прима залежить від використання структури даних для графа та порядку ребер. У таблиці нижче показано деякі варіанти -

Складність часу

Алгоритм Прима можна просто реалізувати за допомогою матриці суміжності або представлення графа списку суміжності, а щоб додати ребро з мінімальною вагою, потрібен лінійний пошук масиву ваг. Для цього потрібно O(|V|²) тривалість роботи. Його можна додатково вдосконалити, використовуючи реалізацію купи для пошуку ребер мінімальної ваги у внутрішньому циклі алгоритму.

Часова складність алгоритму прим становить O(E logV) або O(V logV), де E – номер. ребер, а V – номер. вершин.

Реалізація алгоритму Прима

Тепер давайте подивимося реалізацію алгоритму прима.

програма: Напишіть програму для реалізації алгоритму прима мовою C.

 #include #include #define vertices 5 /*Define the number of vertices in the graph*/ /* create minimum_key() method for finding the vertex that has minimum key-value and that is not added in MST yet */ int minimum_key(int k[], int mst[]) { int minimum = INT_MAX, min,i; /*iterate over all vertices to find the vertex with minimum key-value*/ for (i = 0; i <vertices; 0 i++) if (mst[i]="=" && k[i] < minimum ) min="i;" return min; } * create prim() method for constructing and printing the mst. g[vertices][vertices] is an adjacency matrix that defines graph mst.* void prim(int g[vertices][vertices]) { array of size equal to total number vertices storing mst* int parent[vertices]; k[vertices] selecting edge having weight* k[vertices]; mst[vertices]; i, count,edge,v; *here 'v' vertex* (i="0;" i vertices; mst[i]="0;" k[0]="0;" *it select as first parent[0]="-1;" set value parent[] -1 make it root (count="0;" count vertices-1; count++) *select vertex key not added in mst yet from vertices* mst); mst[edge]="1;" (v="0;" v v++) (g[edge][v] mst[v]="=" g[edge][v] k[v]) parent[v]="edge," k[v]="g[edge][v];" *print constructed spanning tree* printf('
 	 weight
'); printf(' %d 
', parent[i], g[i][parent[i]]); main() 0, 3, 0}, {0, 10, 4, {3, 2, 6}, 1}, 6, 1, }; prim(g); 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/41/prims-algorithm-7.webp" alt="Prim"> <p>So, that&apos;s all about the article. Hope, the article will be helpful and informative to you.</p> <hr></vertices;>