تفاوت بین کروسکال و پریم

2024 نویسنده: Alex Aldridge | [email protected]. آخرین اصلاح شده: 2023-12-17 13:37

Kruskal vs Prim

در علوم کامپیوتر، الگوریتم‌های پریم و کروسکال یک الگوریتم حریصانه هستند که یک درخت پوشا حداقلی را برای یک گراف وزن‌دار متصل به هم پیدا می‌کند. درخت پوشا زیرگراف یک گراف است به طوری که هر گره گراف با یک مسیر که یک درخت است به هم متصل می شود. هر درخت پوشا دارای وزن است و حداقل وزن/هزینه ممکن برای همه درختان پوشا حداقل درخت پوشا (MST) است.

بیشتر درباره الگوریتم Prim

این الگوریتم توسط ریاضیدان چک ووتچ یارنیک در سال 1930 و بعداً به طور مستقل توسط دانشمند کامپیوتر رابرت سی پریم در سال 1957 توسعه یافت. این الگوریتم توسط Edsger Dijkstra در سال 1959 دوباره کشف شد. الگوریتم را می توان در سه مرحله کلیدی بیان کرد.

با توجه به نمودار متصل با n گره و وزن مربوط به هر یال،

1. یک گره دلخواه را از نمودار انتخاب کنید و آن را به درخت T (که اولین گره خواهد بود) اضافه کنید

2. وزن هر یال متصل به گره های درخت را در نظر بگیرید و حداقل را انتخاب کنید. لبه و گره را در انتهای دیگر درخت T اضافه کنید و یال را از نمودار حذف کنید. (در صورت وجود دو یا چند حداقل، یکی را انتخاب کنید)

3. مرحله 2 را تکرار کنید تا n-1 یال به درخت اضافه شود.

در این روش، درخت با یک گره دلخواه شروع می شود و با هر چرخه از آن گره به بعد گسترش می یابد. بنابراین، برای اینکه الگوریتم به درستی کار کند، گراف باید یک گراف متصل باشد. شکل اصلی الگوریتم Prim دارای پیچیدگی زمانی O(V^{2). است.}

بیشتر درباره الگوریتم کروسکال

الگوریتم توسعه یافته توسط جوزف کروسکال در مجموعه مقالات انجمن ریاضی آمریکا در سال 1956 ظاهر شد. الگوریتم کروسکال همچنین می تواند در سه مرحله ساده بیان شود.

با توجه به نمودار با n گره و وزن مربوط به هر یال،

1. کمانی را با کمترین وزن کل نمودار انتخاب کنید و به درخت اضافه کنید و از نمودار حذف کنید.

2. از میان باقیمانده، لبه کم وزن را انتخاب کنید، به گونه ای که یک چرخه تشکیل نشود. لبه را به درخت اضافه کنید و از نمودار حذف کنید. (در صورت وجود دو یا چند حداقل، یکی را انتخاب کنید)

3. فرآیند مرحله 2 را تکرار کنید.

در این روش، الگوریتم با حداقل وزن شروع می شود و به انتخاب هر یال در هر چرخه ادامه می دهد. بنابراین، در الگوریتم، گراف نیازی به اتصال ندارد. الگوریتم کروسکال دارای پیچیدگی زمانی O(logV) است.

تفاوت بین الگوریتم کروسکال و پریم چیست؟

• الگوریتم Prim با یک گره مقداردهی اولیه می شود، در حالی که الگوریتم Kruskal با یک یال شروع می شود.

• الگوریتم های Prim از یک گره به گره دیگر گستردگی دارند در حالی که الگوریتم Kruskal یال ها را به گونه ای انتخاب می کند که موقعیت یال بر اساس آخرین مرحله نباشد.

• در الگوریتم prim، گراف باید یک گراف متصل باشد در حالی که کروسکال می تواند روی نمودارهای قطع شده نیز عمل کند.

• الگوریتم Prim دارای پیچیدگی زمانی O(V^{2)، و پیچیدگی زمانی Kruskal O(logV) است.}