درخت پوشای کمینه¶

کروسکال (Kruskal)¶

یال های گراف را بر حسب وزنشان به صورت صعودی مرتب می کنیم راس های گراف را بدون هیچ یالی درون MST نهایی اضافه می کنیم(فرض کنید داریم قدم به قدم MST را می سازیم و در ابتدای کار این MST بدون هیچ یالی است و قرار است یال های آن را اضافه کنیم). الگوریتم از اولین یال مرتب شده شروع می کند و در هر مرحله یال انتخاب شده را به MST اضافه می کند اگر در MST با یال های انتخاب شده قبلی دور درست نکند. برای فهمیدن اینکه یال انتخاب شده دور تشکیل می دهد یا نه می توانیم از DSU استفاده کنیم. اثبات درستی این الگوریتم به کمک برهان خلف است. فرض کنید MST بدست آمده توسط الگوریتم G باشد و MST اصلی H باشد. کم وزن ترین یالی که در H بکار رفته و در G بکار نرفته را در نظر بگیرید. در الگوریتم کروسکال حتماً از روی این یال رد شدیم و این یال باعث ایجاد دور شده بنابراین H دور دارد و این با فرض H متناقض است. اردر این الگوریتم \(O(mlgn + n)\) است.

پریم (Prim)¶

به طور کل الگوریتم پریم یک مجموعه از رئوس داریم که در هر مرحله یک راس به آن ها با یک یال اضافه می شود و در آخر مجموعه رئوس با مجموعه رئوس اصلی گراف یکسان می شود. برای آشنایی بیشتر با این الگوریتم به دقت به مراحل آن توجه کنید.

• یک مجموعه ایجاد می کنیم که نمایانگر رئوس موجود در MST در هر مرحله این الگوریتم است.
• یک مقدار کمترین فاصله برای تمامی راس های گراف ایجاد می کنیم و مقدار تمامی آن ها را برابر بی نهایت می گذاریم(عددی بزرگ) و برای یک راس دلخواه که اولین راس ما در این الگوریتم است مقدار صفر می گذاریم.
• تا موقعی که مجموعه ما با مجموعه رئوس گراف یکسان نشده این سه کار را انجام می دهیم. در ابتدا یک راس u را انتخاب می کنیم که در مجموعه ما نباشد و کمترین مقدار فاصله را داشته باشد. u را به مجموعه خود اضافه می کنیم و بعد از آن مقدار فاصله تمامی راس های همسایه u را بروز رسانی می کنیم. به این شکل که اگر راس w با یال z به راس u متصل بود و فاصله u به علاوه z کمتر از فاصله w بود فاصله w را برابر فاصله u به علاوه z می کنیم.

توضیح آخر درباره ایده الگوریتم پریم این است که در هر مرحله بین مجموعه راسی که ما انتخاب کردیم و مجموعه رئوس دیگر گراف یالی را انتخاب می کنیم که کمترین وزن را داشته باشد. اثبات الگوریتم به این شکل است که در هر مرحله ما یالی را بین مجموعه خودمان و مجموعه دیگر رئوس انتخاب می کنیم. اگر این یال انتخاب نشود MST همبند نمی شود که تناقض است و اگر دو یال انتخاب شود MST دور پیدا می کند و باز هم تناقض ایجاد می شود. بنابراین باید یک یال انتخاب شود و برای اینکه کمترین وزن را MST داشته باشد باید کمترین یال انتخاب شود که این همان چیزیست که ما انجام می دهیم. اردر این الگوریتم \(O(mlgn + n)\) است.