خبرکاو:

در علوم کامپیوتر، الگوریتم پریم به شما کمک می کند حداقل درخت پوشا یک نمودار را پیدا کنید. این یک الگوریتم حریصانه است - به این معنی که گزینه موجود در لحظه را انتخاب می کند.

در این مقاله، نمایش شبه کد الگوریتم پریم را به شما نشان خواهم داد. اما قبل از آن، بیایید نگاهی عمیق‌تر به الگوریتم پریم بیندازیم.

آنچه را پوشش خواهیم داد

الگوریتم پریم چیست؟

الگوریتم Prim یک نوع الگوریتم حریص برای یافتن حداقل درخت پوشا (MST) یک گراف بدون جهت و وزن است.

حداقل درخت پوشا (MST) زیرمجموعه ای از لبه های یک نمودار است که تمام رئوس (نقطه ای که اضلاع به هم می رسند) را به هم متصل می کند تا وزن کل یال ها بدون تشکیل چرخه به حداقل برسد.

پس ، به خاطر داشته باشید که اگر MST یک نمودار را با الگوریتم Prim پیدا کنید، نباید چرخه ای وجود داشته باشد. یعنی اگر A به B و B به C پیوند دهد، C نمی تواند دوباره به A پیوند دهد زیرا این یک چرخه ایجاد می کند. من تعدادی اینفوگرافیک همراه با توضیحات آماده کردم که به شما در درک بهتر آن در بخش های بعدی این مقاله کمک می کند.

وزن کل لبه ها معمولاً به عنوان cost نیز نامیده می شود. و یکی از اهداف الگوریتم پریم بدست آوردن درخت حداقل هزینه است که رئوس نمودار را پوشش می دهد بدون اینکه هیچ کدام از آنها را پشت سر بگذارد.

پس ، این نکته دیگری است که باید در نظر داشت - همه رئوس باید در به دست آوردن حداقل درخت پوشا (MST) دخیل باشند.

الگوریتم پریم را الگوریتم یارنیک نیز می نامند زیرا در ابتدا توسط ریاضیدان چک ووتچ یارنیک در سال 1930 توسعه یافت. بعداً توسط رابرت سی پریم در سال 1957 دوباره کشف و منتشر شد - از این رو الگوریتم پریم نامگذاری شد.

الگوریتم پریم با شروع از یک راس دلخواه، اضافه کردن حداقل وزنی که درخت را به یک راس جدید متصل می‌کند، کار می‌کند و این فرآیند را تا زمانی که همه راس‌ها در درخت گنجانده شوند، تکرار می‌کند.

نحوه پیاده سازی الگوریتم پریم

برای پیاده سازی الگوریتم پریم در یافتن حداقل درخت پوشا یک گراف، در اینجا سه ​​نکته را باید در نظر داشت:

تمام رئوس نمودار باید گنجانده شود

ابتدا باید راس با حداقل وزن انتخاب شود. همچنین می‌شنوید که برخی از افراد آن وزن را مسافت می‌نامند، اما بیایید آن را وزن بنامیم.

تمام رئوس باید به هم وصل شوند

نباید چرخه ای وجود داشته باشد

نمودار زیر را در نظر بگیرید:

شما باید با انتخاب یک راس دلخواه به عنوان نقطه شروع و اضافه کردن آن به درخت شروع کنید.

برای مرحله بعد باید لبه ای را با حداقل وزنی که یک راس در درخت را به راسی که هنوز در درخت نیست وصل می کند انتخاب کنید و سپس راس جدید را به درخت اضافه کنید.

انتخاب D به عنوان راس شروع به این نتیجه رسید:

به این شکل اتفاق افتاد:

D نقطه شروع بود

حداقل وزن بعدی متصل به D 2 است - خط بین D و C پس ، من آن را انتخاب کردم.

با نگاهی به راس C ، حداقل وزن بعدی آن 1 است - خط بین C و A پس ، آن را به عنوان بعدی انتخاب کردم

با نگاه کردن به A ، خطوط 2 و 4 به آن متصل می شوند. ما نمی توانیم 4 انتخاب کنیم زیرا بزرگتر از 2 است و ما را به نقطه شروع D هدایت می کند. پس ، ما باید 2 انتخاب کنیم - خط اتصال رئوس A و B

با نگاه کردن به B ، خط 3 آن را به C و خط 7 آن را به E متصل می کند. ما نمی‌توانیم خط 3 را انتخاب کنیم زیرا یک چرخه بین C ، A و B تشکیل می‌دهد. ما همچنین باید قبل از انتخاب خط 7 دو بار فکر کنیم زیرا عدد بزرگی است. یک خط 4 وجود دارد که C به G متصل می کند، پس ، من آن را انتخاب کردم

در راس G ، یک اتصال به F با خط 1 و خط 3 به E وجود دارد، پس حداقل وزن را انتخاب می کنم که 1 باشد.

در این نقطه، E تنها راس است که هنوز متصل نشده است. اتصال آن امکان پذیر است زیرا در هیچ نقطه ای چرخه ای تشکیل نمی دهد. پس ، آن را وصل کردم.

در اینجا اتصال گام به گام است:

باز هم، این همان چیزی است که تمام نکات بالا به آن منجر می شود:

هزینه مجموع تمام وزن های متصل به رئوس است. اینطوری 13 گرفتم.

این روند تا زمانی ادامه می یابد که تمام رئوس به درخت اضافه شود. هیچ یک از آنها را پشت سر نمی گذارد و چرخه ای تشکیل نمی دهد.

شما می توانید هر یک از رئوس را نقطه شروع قرار دهید. اگر از راس A شروع کنم این نتیجه می شود:

و این نتیجه اگر از راس C شروع کنم:

نمونه شبه کد الگوریتم پریم

در زیر تعدادی شبه کد برای اجرای الگوریتم پریم آورده شده است. من همچنین نظراتی را درج کرده ام تا بتوانید موارد را در حین وقوع آنها پیگیری کنید:

 prim(graph): # Initialize an empty set to hold the vertices in the minimum spanning tree mst = empty set # Select the first vertex to start the tree startVertex = first vertex in graph mst.add(startVertex) # Initialize the set of edges to consider edges = edges connected to startVertex # Iterate until all vertices are in the minimum spanning tree while mst has fewer vertices than graph: # Find the minimum edge in the set of edges minEdge, minWeight = findMinEdge(edges) # Add the vertex to the minimum spanning tree mst.add(minEdge) # Add the edges connected to the vertex to the set of edges to consider for edge in edges connected to minEdge: if edge is not in mst: edges.add(edge) # Remove the minimum edge from the set of edges to consider edges.remove(minEdge) # Return the minimum spanning tree as an array return mst as an array

نحوه پیاده سازی الگوریتم Prim در جاوا اسکریپت با استفاده از کد شبه

با استفاده از آن شبه کد، می توانید الگوریتم Prim را در جاوا اسکریپت به این ترتیب پیاده سازی کنید:

 // Define a graph as an adjacent list const graph = { 'A': {'B': 4, 'C': 2}, 'B': {'A': 4, 'C': 1, 'D': 5}, 'C': {'A': 2, 'B': 1, 'D': 8, 'E': 10}, 'D': {'B': 5, 'C': 8, 'E': 2}, 'E': {'C': 10, 'D': 2} }; // Find the minimum edge in the edge list function findMinEdge(edges) { let minEdge = null; let minWeight = Infinity; for (const [v, weight] of Object.entries(edges)) { if (weight < minWeight) { minEdge = v; minWeight = weight; } } return [minEdge, minWeight]; } // Find the minimum spanning tree using Prim's algorithm function prim(graph) { // Initialize an empty set to hold the vertices in the MST const mst = new Set(); // Select the first vertex to start the tree const startVertex = Object.keys(graph)[0]; mst.add(startVertex); // Initialize the set of edges to consider const edges = graph[startVertex]; // Iterate over the graph object until all vertices are in the MST while (mst.size < Object.keys(graph).length) { // Find the minimum edge in the set of edges const [minEdge, minWeight] = findMinEdge(edges); // Add the vertex to the MST mst.add(minEdge); // Add the edges connected to the vertex to the set of edges to consider for (const [v, weight] of Object.entries(graph[minEdge])) { if (!mst.has(v)) { edges[v] = weight; } } // Remove the minimum edge from the set of edges to consider delete edges[minEdge]; } // Return the MST as an array return Array.from(mst); } // Call the prim function with the graph object const minimumSpanningTree = prim(graph); // Log the result to the console console.log(minimumSpanningTree); // Result: ['A', 'C', 'B', 'D', 'E']

نتیجه

الگوریتم پریم یک الگوریتم سرگرم کننده و مفید است که در زندگی روزمره برای حل مسائل استفاده می شود. به همین دلیل است که این مقاله به نشان دادن چیستی آن و یک مثال شبه کد اختصاص داده شده است که با آن می توانید آن را به هر زبانی پیاده سازی کنید.

اگر نمی دانید که چه چیزی می توانید از الگوریتم Prim استفاده کنید، در اینجا برخی از کاربردهای آن آورده شده است:

طراحی شبکه های حمل و نقل

ساخت درختان فیلوژنتیک در بیوانفورماتیک

تقسیم بندی تصاویر بر اساس رنگ و شدت پیکسل

گروه بندی اشیاء مشابه با هم در الگوریتم های خوشه بندی

ممنون که خواندید.