В тази статия ще обсъдим алгоритъма на прим. Заедно с алгоритъма ще видим и сложността, работата, примера и изпълнението на алгоритъма на prim.

Преди да започнем основната тема, трябва да обсъдим основните и важни термини като spanning tree и minimal spanning tree.

Spanning Tree - Обхващащото дърво е подграф на неориентиран свързан граф.

Минимално обхващащо дърво - Минималното обхващащо дърво може да се дефинира като обхващащо дърво, в което сумата от теглата на ръба е минимална. Теглото на обхващащото дърво е сумата от теглата, дадени на ръбовете на обхващащото дърво.

Сега да започнем основната тема.

Алгоритъмът на Прим е алчен алгоритъм, който се използва за намиране на минималното обхващащо дърво от графика. Алгоритъмът на Prim намира подмножеството от ръбове, което включва всеки връх на графиката, така че сумата от теглата на ръбовете да може да бъде минимизирана.

Алгоритъмът на Prim започва с единичния възел и изследва всички съседни възли с всички свързващи ръбове на всяка стъпка. Бяха избрани ръбовете с минимални тегла, които не причиняват цикли в графиката.

Как работи алгоритъмът на прим?

Алгоритъмът на Prim е алчен алгоритъм, който започва от един връх и продължава да добавя ръбовете с най-малко тегло, докато целта бъде достигната. Стъпките за прилагане на алгоритъма на прим са дадени както следва -

• Първо, трябва да инициализираме MST с произволно избрания връх.
• Сега трябва да намерим всички ръбове, които свързват дървото в горната стъпка с новите върхове. От намерените ръбове изберете минималния ръб и го добавете към дървото.
• Повторете стъпка 2, докато се формира минималното обхващащо дърво.

Приложенията на алгоритъма на прим са -

• Алгоритъмът на Prim може да се използва при проектирането на мрежи.
• Може да се използва за създаване на мрежови цикли.
• Може да се използва и за полагане на електрически кабели.

Пример за алгоритъм на прим

Сега, нека видим работата на алгоритъма на prim, използвайки пример. Ще бъде по-лесно да разберете алгоритъма на прим, като използвате пример.

Да предположим, че една претеглена графика е -

Етап 1 - Първо, трябва да изберем връх от горната графика. Да изберем Б.

конвертиране на низ в java

Стъпка 2 - Сега трябва да изберем и добавим най-късия ръб от връх B. Има два ръба от връх B, които са B до C с тегло 10 и ръб B към D с тегло 4. Сред ръбовете ръбът BD има минималното тегло . Така че, добавете го към MST.

Стъпка 3 - Сега отново изберете ръба с минимално тегло сред всички останали ръбове. В този случай ръбовете DE и CD са такива ребра. Добавете ги към MST и проучете съседните на C, т.е. E и A. И така, изберете ръба DE и го добавете към MST.

Стъпка 4 - Сега изберете edge CD и го добавете към MST.

Стъпка 5 - Сега изберете ръба CA. Тук не можем да изберем ръба CE, тъй като това би създало цикъл към графиката. И така, изберете крайния CA и го добавете към MST.

И така, графиката, получена в стъпка 5, е минималното обхващащо дърво на дадената графика. Цената на MST е дадена по-долу -

Цена на 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 

Сложност на алгоритъма на Прим

Сега нека видим времевата сложност на алгоритъма на Прим. Времето за работа на алгоритъма на прим зависи от използването на структурата от данни за графиката и подреждането на ръбовете. Таблицата по-долу показва някои възможности за избор -

Времева сложност

Алгоритъмът на Prim може просто да се приложи чрез използване на матрицата на съседство или графичното представяне на списъка на съседство, а за добавяне на ръба с минимално тегло е необходимо линейно търсене на масив от тегла. Изисква O(|V|²) време на работа. Може да се подобри допълнително чрез използване на имплементацията на heap за намиране на ръбовете с минимално тегло във вътрешния цикъл на алгоритъма.

Времевата сложност на алгоритъма на прим е O(E logV) или O(V logV), където E е номерът. на ръбовете, а V е номерът. от върхове.

Реализация на алгоритъма на Прим

Сега нека видим изпълнението на алгоритъма на prim.

програма: Напишете програма за прилагане на алгоритъма на прим на език 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;>