الگوریتم پریم
From Wikipedia, the free encyclopedia
الگوریتم پریم، الگوریتمی در نظریه گرافها است که زیردرخت پوشای کمینه را برای یک گراف همبند وزن دار پیدا میکند یعنی زیرمجموعهای از یالها را در آن گراف مییابد که درختی را تشکیل میدهند که همه رئوس را شامل میشود در حالیکه مجموع وزن همه آن یالها کمینه شدهاست. این الگوریتم در سال ۱۹۳۰ توسط ریاضیدانی به نام جارنیک داده شد و سپس در سال ۱۹۵۷ پریم، دانشمند علوم کامپیوتر آن را مستقل از جارنیک کشف کرد و در سال ۱۹۵۹ دایکسترا دوباره به آن دست یافت. از این رو این الگوریتم گاهی با نام الگوریتم DJP نیز شناخته میشود که برگرفته از اسامی دایکسترا، جارنیک و پریم است.