خوارزمية Prim Prim's Algorithm

الصياغة

import heapq
visited = {start}
pq = [(w, start, v) for v, w in graph[start]]
heapq.heapify(pq)
while pq:
    weight, u, v = heapq.heappop(pq)
    if v in visited:
        continue
    visited.add(v)
    mst_weight += weight
    for neighbor, w in graph[v]:
        if neighbor not in visited:
            heapq.heappush(pq, (w, v, neighbor))

📄 مثال

import heapq

def prim(graph, start):
    visited = {start}
    pq = [(w, start, v) for v, w in graph[start]]
    heapq.heapify(pq)
    mst_weight = 0
    mst_edges = []
    while pq and len(visited) < len(graph):
        weight, u, v = heapq.heappop(pq)
        if v in visited:
            continue
        visited.add(v)
        mst_weight += weight
        mst_edges.append((u, v, weight))
        for neighbor, w in graph[v]:
            if neighbor not in visited:
                heapq.heappush(pq, (w, v, neighbor))
    return mst_weight, mst_edges

graph = {"A": [("B", 6), ("C", 2)], "B": [("A", 6), ("D", 3)], "C": [("A", 2), ("D", 1)], "D": [("B", 3), ("C", 1)]}
print(prim(graph, "A"))

أهم النقاط

💡 نصائح عملية

• لرسم بياني كثيف جدًا (قريب من كامل)، تطبيق Prim بمصفوفة جوار بسيطة O(V²) قد يكون أسرع عمليًا من نسخة الكومة رغم التعقيد النظري الأعلى للرمز البسيط

⚠️ أخطاء شائعة

• الخلط بينها وبين Dijkstra لتشابه الكود — Prim تقارن وزن الضلع المباشر فقط، بينما Dijkstra تقارن مجموع المسار الكلي من المصدر

خصائص ذات صلة