الگوریتم Kruskal
Kruskal's AlgorithmKruskal یک Minimum Spanning Tree می‌سازد: edgeها را بر اساس weight مرتب می‌کند و هر بار ارزان‌ترین edgeای را می‌گیرد که cycle نسازد.
اول این مفهوم را در ذهن نگه دار
Kruskal یک Minimum Spanning Tree می‌سازد: edgeها را بر اساس weight مرتب می‌کند و هر بار ارزان‌ترین edgeای را می‌گیرد که cycle نسازد.
چطور کار می‌کند؟ ساده و مرحله‌ای
edgeها را صعودی sort کن.
با Union-Find بررسی کن دو endpoint از قبل connected هستند یا نه؛ اگر نیستند edge را اضافه و componentها را union کن.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
مشخص کن گراف directed/undirected و weighted/unweighted است.
representation گراف را انتخاب کن.
state الگوریتم و حالت disconnected/cycle را صریح مدیریت کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای الگوریتم Kruskal هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
O(E log E)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- فقط وقتی assumptionهای الگوریتم با مسئله گراف هماهنگ است از آن استفاده کن.
کجا معمولاً اشتباه می‌کنیم؟
- فراموش کردن componentهای disconnected.
- قاطی کردن shortest path وزن‌دار و بدون وزن.
- مدیریت نکردن revisit/cycle.
مدل یک پاسخ حرفه‌ای
Kruskal را به Union-Find وصل کن. معمولاً sort کردن edgeها هزینه غالب و حدود O(E log E) است.
الگوریتم Kruskal چه مسئله‌ای را حل می‌کند؟
Kruskal یک Minimum Spanning Tree می‌سازد: edgeها را بر اساس weight مرتب می‌کند و هر بار ارزان‌ترین edgeای را می‌گیرد که cycle نسازد.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا O(E log E) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
فراموش کردن componentهای disconnected.