درختِ پوشایِ کمینه یا MST مجموعِ وزنِ یال‌هایِ اتصالِ تمامِ گره‌هایِ یک گرافِ بی‌جهتِ پیوسته را کمینه می‌کند. این هدف با کوتاه‌ترینِ مسیر ازیک مبدأ به مقصد فرق دارد. درمثالِ اصیلِ این صفحه،MST مجموعِ ۶دارد اما مسیرِ دوگره درونِ آن۶و کوتاه‌ترینِ مسیرِ همان دوگره درگرافِ اصلی۳است. هرسه عدد واقعاً محاسبه می‌شوند.
چهار گره وپنج یال
گره‌هایِ A،B،C وD را داریم. یال‌هایِ بی‌جهتِ AB،BC وCD وزنِ ۲؛وAD وAC وزنِ ۳ دارند. این وزن‌ها واحدِ آموزشیِ ساختگی‌اند؛ هزینهٔواقعیِ شبکه،قیمت یا مدتِ سرویس نیستند. برایِ درختِ پوشایِ چهارگرهیِ پیوسته سه یال لازم است،اما هر سه یالِ ارزانِ دلخواه لزوماًگراف را بدونِ چرخه وصل نمی‌کنند.
در اجرایِ Kruskalِ ما،یال‌ها ابتدا باوزن مرتب می‌شوند ودر تساوی،نامِ دو سرِ یال سیاستِ قطعیِ همین تمرین را می‌سازد. ساختارِ union-find مؤلفهٔاتصال را نگه می‌دارد. یال فقط وقتی پذیرفته می‌شود که دو سرش اکنون دردو مؤلفهٔجدا باشند؛ درغیراین‌صورت چرخه می‌سازد وکنار می‌رود.
دفترِ پذیرش و ردِ یال‌ها
ابتداAB،بعدBC وCD پذیرفته می‌شوند وهرچهارگره وصل‌اند؛ مجموع۲+۲+۲=۶ است. دو یالِ وزنِ ۳ِ باقی دراین وضعیت دو سرِ ازپیش‌متصل دارند ودر trace رد می‌شوند. کد صرفاًخروجیِ سه یال را چاپ نکرده؛ دلیلِ take یاreject هر یال را نگه می‌دارد و با ورودیِ وارونه هم همان درخت را دراین سیاست می‌سازد.
| یال | وزن | نتیجه درهمین ترتیب |
|---|---|---|
| AB | ۲ | پذیرش؛دو مؤلفه وصل می‌شوند |
| BC | ۲ | پذیرش |
| CD | ۲ | پذیرش؛تمامِ گره‌ها وصل‌اند |
| AC وAD | ۳ | رد؛اتصالِ درونِ همان مؤلفه |
یک درختِ کمینه الزاماًدرهمهٔگراف‌ها یکتا نیست. تساویِ وزن و سیاستِ ترتیب ممکن است شاهدِ دیگری باهمان مجموع بسازد. قطعی‌کردنِ نمایشِ این مثال،اثباتِ یکتاییِ پاسخِ همهٔورودی‌ها نیست.
همهٔانتخاب‌هایِ سه‌یالی را مستقل بررسی کنیم
ازپنج یال،ده زیرمجموعهٔسه‌تایی داریم. oracleِ مستقل هرکدام را با پیمایشِ مسیرهایِ کوچک بررسی می‌کند و فقط انتخاب‌هایی را نگه می‌دارد که تمامِ گره‌ها را ازA دسترس‌پذیر کنند. درگرافِ سادهٔچهارگرهی با سه یال،اتصال یعنی درخت؛ هزینهٔهمهٔشاهدهایِ پوشا ثبت و کمترینِ آن‌ها۶می‌شود.
این شمارشِ کامل جایگزینِ عملیِ عمومی برایِ گرافِ بزرگ نیست؛ فقط مرجعِ مستقلِ ده‌حالتیِ ماست. زمان،حافظه یا حدِ مقیاسِ Kruskal بنچمارک نشده‌اند وJavaِ منبع هم اجرا نشده است. تمامِ محاسبه‌ها در Python۳٫۱۲٫۱۴ باعددِ صحیح انجام شده‌اند.
چرا مسیرِ داخلِ MST کوتاه‌ترینِ مسیر نیست؟
درگرافِ اصلی،راهِ مستقیمِ A→D وزنِ ۳دارد. دردرختِ پیداشده فقطA→B→C→D وجود دارد ووزنِ آن۶است. همهٔمسیرهایِ سادهٔAتاD درگرافِ اصلی جدا شمرده می‌شوند وکمترینِ هزینه۳است؛ مسیرِ درخت هم دوباره رویِ یال‌هایِ خودش محاسبه می‌شود.
درخت برایِ کمینه‌کردنِ مجموعِ اتصالِ همه انتخاب شده است،نه کمینه‌کردنِ تک‌تکِ فاصله‌ها ازA. بنابراین درختِ کشفِ BFS یا درختِ کوتاه‌ترینِ مسیرِ دایکسترا را صرفاًبه‌دلیلِ درخت‌بودن,MST نمی‌نامیم. هدفِ تابعِ هزینه باید کنارِ نامِ الگوریتم روشن باشد.
وقتی گرهٔجدا داریم،جنگل می‌سازیم
U را بدونِ هیچ یال اضافه می‌کنیم. حالا خروجی دو مؤلفه وسه یال دارد؛ شرطِ تعدادِ یال برابرِ|V|−تعدادِ مؤلفه‌ها کنترل می‌شود. نامِ درست دراین حالت spanning forest است،نه یک درختِ وصل‌کنندهٔهمهٔپنج گره. دو fixtureِ دوگرهیِ جدا باوزنِ−۱وصفر نیز پذیرفته می‌شوند؛ وزنِ منفی درMSTِ بی‌جهتِ این دامنه با مسئلهٔمسیرِ کمینه یکی نیست.
دایکسترا هدفِ مسیرِ وزن‌دار و BFS/DFS پیمایش را جدا توضیح می‌دهند. ادامه در مبانی هوش مصنوعی؛ ازاین گرافِ کوچک،طرحِ خرید،بهینه‌سازیِ عملیاتی یا کاهشِ هزینهٔمحصولِ اپرا نتیجه نمی‌شود.
فایل تمرین و منبع
کد مستقلِ تمرینِ محدود · تمام خروجیِ واقعیِ همین تمرین؛ JSON
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.