الگوریتم میانگین–خطی درخت پوشای کمینه یک الگوریتم تصادفی برای یافت درخت پوشای کمینه در یک گراف وزن دار بدون راس تنها است.این الگوریتم توسط David Karger، فیلیپ کلین و Robert Tarjan ابداع شده است. این الگوریتم متکی بر شیوه الگوریتم بروکا است که برای یافت درخت پوشای کمینه در زمانی خطی است. این الگوریتم تشکیل شده از الگوریتم تقسیم و حل، الگوریتم حریصانه و الگوریتم های تصادفی برای رسیدن به زمان خطی مور...
