نظرة عامة شاملة حول خوارزمية بريم

في علوم الحاسوب، تعد خوارزمية بريم Prim's algorithm (المعروفة أيضًا باسم خوارزمية Jarník) هي خوارزمية جشعة تعثر على الحد الأدنى من الشجرة الممتدة لرسم بياني مرجح غير موجه (weighted undirected graph). هذا يعني أنه يعثر على مجموعة فرعية من الحواف التي تشكل شجرة تتضمن كل رأس، حيث يجري تقليل الوزن الإجمالي لجميع حواف الشجرة إلى أدنى حد. تعمل الخوارزمية عن طريق بناء هذه الشجرة باستخدام رأسًا واحدًا في كل مرة، وتبدأ برأس عشوائية، في كل خطوة تضيف أرخص اتصال ممكن من الشجرة إلى رأس أخرى.

قام عالم الرياضيات التشيكي Vojtěch Jarník بتطوير الخوارزمية في عام 1930، ثم أعاد اكتشافها ونشرها من علماء الحاسوب Robert C. Prim في عام 1957 وEdsger W. Dijkstra في عام 1959. لذلك، يطلق عليها أحيانًا خوارزمية جارنيك، أو خوارزمية Prim – Jarník، أو خوارزمية Prim – Dijkstra أو خوارزمية DJP.

تشمل الخوارزميات الأخرى المعروفة لهذه المشكلة خوارزمية Kruskal وخوارزمية Borůvka. تجد هذه الخوارزميات الحد الأدنى من مجموعة التفرعات الممتدة في رسم بياني محتمل غير متصل ؛ في المقابل، فإن الشكل الأساسي لخوارزمية بريم لا يجد سوى الحد الأدنى من الأشجار الممتدة في الرسوم البيانية المتصلة. ومع ذلك، عند تشغيل خوارزمية بريم بشكل منفصل لكل مكون متصل بالرسم البياني، يمكن أيضًا استخدامها للعثور على الحد الأدنى من مجموعة التفرعات الممتدة. من حيث تعقيدها الزمني المقارب، فإن هذه الخوارزميات الثلاثة متساوية في السرعة بالنسبة للرسوم البيانية المتفرقة، ولكنها أبطأ من الخوارزميات الأخرى الأكثر تعقيدًا. ومع ذلك، بالنسبة للرسوم البيانية الكثيفة بما فيه الكفاية، يمكن عمل خوارزمية بريم للعمل في الوقت الخطي، أو تلبية أو تحسين الحدود الزمنية للخوارزميات الأخرى.