الگوریتم پریم (Prim's Algorithm)+کد پایتون

الگوریتم پریم (Prim's Algorithm) یک روش معروف برای یافتن درخت پوشای کمینه (Minimum Spanning Tree, MST) در یک گراف وزن‌دار و بدون جهت است. درخت پوشای کمینه یک زیرگراف است که شامل تمام رئوس گراف اصلی می‌شود و دارای کمترین مجموع وزن یال‌ها است. الگوریتم پریم برای کاربردهایی مانند طراحی شبکه، برنامه‌ریزی شهری، و ساختارهای داده‌ای مورد استفاده قرار می‌گیرد.

مراحل الگوریتم پریم

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

ویژگی‌ها

• حریصانه: الگوریتم پریم یک الگوریتم حریصانه است، به این معنی که در هر مرحله بهترین انتخاب ممکن (در اینجا کوتاه‌ترین یال) را انجام می‌دهد.
• کارایی: الگوریتم پریم در گراف‌هایی با تعداد یال‌های زیاد و تعداد رئوس نسبتاً کم کارآمد است.

کاربردها

• شبکه‌های ارتباطی: برای طراحی شبکه‌هایی با کمترین هزینه کابل‌کشی.
• طراحی مدار: در طراحی مدارهای الکتریکی و الکترونیکی.
• برنامه‌ریزی شهری: برای طراحی و برنامه‌ریزی زیرساخت‌های شهری.

مثال

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

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

کد پایتون

این کد از یک صف اولویت برای انتخاب کم‌هزینه‌ترین یال در هر مرحله استفاده می‌کند:

import heapq


def prim(graph, start_vertex):
    visited = set([start_vertex])
    edges = [(cost, start_vertex, to) for to, cost in graph[start_vertex].items()]
    heapq.heapify(edges)

    mst_cost = 0
 mst_edges = []

 while edges:
        cost, from_vertex, to_vertex = heapq.heappop(edges)
 if to_vertex not in visited:
            visited.add(to_vertex)
            mst_cost += cost
            mst_edges.append((from_vertex, to_vertex, cost))

 for to_next, cost_next in graph[to_vertex].items():
 if to_next not in visited:
                    heapq.heappush(edges, (cost_next, to_vertex, to_next))

 return mst_cost, mst_edges


# مثال: گراف وزن‌دار
graph = {
 'A': {'B': 2, 'C': 3},
 'B': {'A': 2, 'C': 1, 'D': 1, 'E': 4},
 'C': {'A': 3, 'B': 1, 'F': 5},
 'D': {'B': 1, 'E': 1},
 'E': {'B': 4, 'D': 1, 'F': 1},
 'F': {'C': 5, 'E': 1, 'G': 1},
 'G': {'F': 1}
}

mst_cost, mst_edges = prim(graph, 'A')
print(&quotCost of MST:&quot, mst_cost)
print(&quotEdges in MST:&quot, mst_edges)

در این کد، graph یک دیکشنری است که گراف وزن‌دار را نمایش می‌دهد. هر کلید نمایانگر یک راس است و مقادیر آن یک دیکشنری دیگر هستند که رئوس متصل به آن راس و وزن یال‌های متصل به آن‌ها را نشان می‌دهد.

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

نتیجه نهایی شامل هزینه کل درخت پوشای کمینه (MST) و لیست یال‌هایی است که در MST قرار دارند: