في هذه المقالة، سنناقش خوارزمية Prim. جنبًا إلى جنب مع الخوارزمية، سنرى أيضًا مدى تعقيد خوارزمية prim وعملها ومثالها وتنفيذها.

قبل البدء بالموضوع الرئيسي يجب أن نناقش المصطلحات الأساسية والمهمة مثل الشجرة الممتدة والحد الأدنى من الشجرة الممتدة.

تمتد شجرة - الشجرة الممتدة هي رسم بياني فرعي لرسم بياني متصل غير موجه.

الحد الأدنى الشجرة الممتدة - يمكن تعريف الحد الأدنى من الشجرة الممتدة على أنها الشجرة الممتدة التي يكون فيها مجموع أوزان الحافة هو الحد الأدنى. وزن الشجرة الممتدة هو مجموع الأوزان الممنوحة لحواف الشجرة الممتدة.

والآن لنبدأ بالموضوع الرئيسي.

خوارزمية بريم هي خوارزمية جشعة تُستخدم للعثور على الحد الأدنى من الشجرة الممتدة من الرسم البياني. تعثر خوارزمية Prim على المجموعة الفرعية من الحواف التي تتضمن كل قمة في الرسم البياني بحيث يمكن تقليل مجموع أوزان الحواف إلى الحد الأدنى.

تبدأ خوارزمية Prim بالعقدة الفردية وتستكشف جميع العقد المجاورة مع جميع الحواف المتصلة في كل خطوة. تم تحديد الحواف ذات الأوزان الدنيا التي لا تسبب أي دورات في الرسم البياني.

كيف تعمل خوارزمية Prim؟

خوارزمية بريم هي خوارزمية جشعة تبدأ من قمة واحدة وتستمر في إضافة الحواف ذات الوزن الأصغر حتى الوصول إلى الهدف. يتم إعطاء خطوات تنفيذ خوارزمية Prim على النحو التالي -

• أولاً، يتعين علينا تهيئة MST بالرأس الذي تم اختياره عشوائيًا.
• الآن، علينا أن نجد جميع الحواف التي تربط الشجرة في الخطوة أعلاه بالقمم الجديدة. من الحواف التي تم العثور عليها، حدد الحد الأدنى للحافة وأضفها إلى الشجرة.
• كرر الخطوة 2 حتى يتم تشكيل الحد الأدنى من الشجرة الممتدة.

تطبيقات خوارزمية برايم هي -

• يمكن استخدام خوارزمية Prim في تصميم الشبكات.
• يمكن استخدامه لعمل دورات الشبكة.
• ويمكن استخدامه أيضًا لوضع كابلات الأسلاك الكهربائية.

مثال على خوارزمية Prim

الآن، دعونا نرى عمل خوارزمية prim باستخدام مثال. سيكون من الأسهل فهم خوارزمية الأولية باستخدام مثال.

لنفترض أن الرسم البياني المرجح هو -

الخطوة 1 - أولا، علينا أن نختار قمة من الرسم البياني أعلاه. لنختار ب.

ما هو غيغابايت

الخطوة 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 موضحة أدناه -

تكلفة 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|²) وقت الركض. يمكن تحسينه بشكل أكبر باستخدام تطبيق الكومة للعثور على الحد الأدنى من حواف الوزن في الحلقة الداخلية للخوارزمية.

التعقيد الزمني لخوارزمية الأولية هو 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;>