حداقل درختان پوشش داده شده برای اتصال تمام گره ها در یک نمودار با حداقل وزن لبه کامل استفاده می شود، دو الگوریتم رایج برای پیدا کردن این درختان الگوریتم های Kruskal و Prim هستند. هر دو کارآمد هستند اما در رویکرد و پیاده سازی متفاوت هستند.

الگوریتم Kruskal

الگوریتم Kruskal همه لبه ها را در نمودار با وزن اضافه می کند، سپس لبه ها را به درخت های پوش اضافه می کند، از کوچکترین شروع می شود، اطمینان حاصل می کند که هیچ چرخه ای تشکیل نمی شود.این فرایند تا زمانی که تمام گره ها متصل شوند ادامه می یابد.

الگوریتم به ویژه برای گراف های پراکنده موثر است.از ساختار داده های تنظیم شده جدا استفاده می کند تا به طور موثر بررسی کند که آیا اضافه کردن لبه یک چرخه ایجاد می کند.

الگوریتم نخست

الگوریتم اولیه از یک گره خودسرانه شروع می شود و با اضافه کردن کوچکترین لبه ای که درخت را به یک گره جدید متصل می کند، درخت را رشد می کند.

این روش اغلب برای گراف های متراکم ترجیح داده می شود، از یک صف اولویت برای انتخاب لبه بعدی با حداقل وزن موثر استفاده می کند.

مقایسه و پیاده سازی

هر دو الگوریتم تضمین می کنند که حداقل درخت پوش دار را پیدا کنید، اما بهره وری آنها بستگی به ساختار گراف دارد. Kruskal ساده تر است که با تمرکز بر لبه های مرتب سازی پیاده سازی، پیاده سازی شود، در حالی که Prim می تواند با گراف های متراکم با استفاده از یک صف اولویت کارآمد تر باشد.

  • انواع Kruskal در سراسر جهان
  • درخت نخست از یک گره شروع رشد می کند
  • هر دو از ساختارهای مختلف داده برای بهره وری استفاده می کنند
  • انتخاب بستگی به چگالی گراف و اندازه دارد