کد هایی که این دفعه قراره یه جورایی توضیح بدیم عبارته از کوروسکال و پرایم ...
کد ها ...
کوروسکال : هدف این الگوریتم پیدا کردن یک درخت اِه که همه ی راس ها رو شامل بشه مجموع یال هاشَم مینیمم باشن ...
تو این الگوریتم اول یال ها رو sort می کنیم ...
بعدش با حرکت رو یال ها اونایی رو که دور ایجاد نمی کنن رو به جواب اضافه می کنیم ... (درخت مورد نظر)
اثبات : برهان خلف ... فرض کنیم درخت فراگیری با مجموع یال های کمتری موجود باشد ... اولین یالی که در این درخت نبود ولی آن را انتخاب کردیم را درنظر میگیریم ...
این یال را به درخت اضافه میکنیم یک دور ایجاد میشود ... یالی در این دور وجود دارد که از این یال سنگینتر است اگر آن را حذف کنیم درختی سبک تر بدست می آید که با بهینه بودن درخت مفروض در تناقض است.
واسه این که بفهمیم یه یال دور ایجاد میکنه یا نه یه چیزی هست بهش میگن disjoint set !! (برین خودتون بخونید !!)
پیچیدگی : سورت کردن یال ها از اوردر eloge و disjoint set هم از اوردر nlogn اِه ... ( اصلِش nlog*n اِه البته ... )
پرایم : هدف این الگوریتم هم پیدا کردن یک درخت اِه که همه ی راس ها رو شامل بشه مجموع یال هاشَم مینیمم باشن ... (مثل همون قبلی اِه !!)
تو این یکی الگوریتم ۲ تا مجموعه در نظر میگیریم ... x , y ...
تعریف x : راس هایی که توشون جواب مساله رو پیدا کردیم ... تعریف y : بقیه ی راس ها ...
حالا تو هر مرحله بین یال های بین ۲ مجموعه!! مینیمم رو به جواب اضافه می کنیم ...
(که متعاقبا یه راس جدیدبه x اضافه می شه)
حالا اگه این کار رو (n-1) بار انجام بدیم درخت مورد نظر رو بدست آوردیم ...
اثبات : برهان خلف ... درخت بهینه را t در نظر بگیرید ...
اولین یالی که در جواب ما هست ولی در t نیست را در نظر بگیرید - طبق روند حرکت الگوریتم ! - (این یال را e بنامید) ...
آن را به t اضافه کنید ... یک دور ایجاد می شود (این دور را c بنامید) ...
که در آن e ماکسیمم یال است ... (وگرنه درخت t بهینه نیست)
حال در الگوریتم خود زمانی را که یال e را به جواب اضافه می کنیم در نظر می گیریم ...
یک سری از راس های c در مجموعه ی x هستند و بقیشون تو y ... یالی در درخت t وجود دارد که این دو مجموعه را به هم وصل کرده است ...این یال از یال e کوچکتر است ... در نتیجه تناقض !! ...
پ.ن: یکم فکرم بد نیست ... :-"
برای بدست آوردن یال مینیمم بین دو مجموعه از set استفاده میکنیم , هر یال حداکثر یک بار وارد set و یک بار خارج میشود درنتیجه الگوریتم از اوردر eloge است.
دو الگوریتم بالا هر دو درخت پوشای کمینه (MST) را پیدا می کند ...
اما به نظر من پیاده سازی الگوریتم کروسکال ساده تره .... ولی در کل صَلاح مملکت خویش خسروان دانند ...
درس زندگی : سعی کنید کد های این الگوریتم ها رو یه چند باری بزنید که یه وقت اگه وسط کانتستی, چیزی به دردتون خورد بدون باگ بزنیدشون .... (همه کد هایی که گذاشتیم نه فقط این ۲ تا ... )
این یال را به درخت اضافه میکنیم یک دور ایجاد میشود ... یالی در این دور وجود دارد که از این یال سنگینتر است اگر آن را حذف کنیم درختی سبک تر بدست می آید که با بهینه بودن درخت مفروض در تناقض است.
واسه این که بفهمیم یه یال دور ایجاد میکنه یا نه یه چیزی هست بهش میگن disjoint set !! (برین خودتون بخونید !!)
پیچیدگی : سورت کردن یال ها از اوردر eloge و disjoint set هم از اوردر nlogn اِه ... ( اصلِش nlog*n اِه البته ... )
پرایم : هدف این الگوریتم هم پیدا کردن یک درخت اِه که همه ی راس ها رو شامل بشه مجموع یال هاشَم مینیمم باشن ... (مثل همون قبلی اِه !!)
تو این یکی الگوریتم ۲ تا مجموعه در نظر میگیریم ... x , y ...
تعریف x : راس هایی که توشون جواب مساله رو پیدا کردیم ... تعریف y : بقیه ی راس ها ...
حالا تو هر مرحله بین یال های بین ۲ مجموعه!! مینیمم رو به جواب اضافه می کنیم ...
(که متعاقبا یه راس جدیدبه x اضافه می شه)
حالا اگه این کار رو (n-1) بار انجام بدیم درخت مورد نظر رو بدست آوردیم ...
اثبات : برهان خلف ... درخت بهینه را t در نظر بگیرید ...
اولین یالی که در جواب ما هست ولی در t نیست را در نظر بگیرید - طبق روند حرکت الگوریتم ! - (این یال را e بنامید) ...
آن را به t اضافه کنید ... یک دور ایجاد می شود (این دور را c بنامید) ...
که در آن e ماکسیمم یال است ... (وگرنه درخت t بهینه نیست)
حال در الگوریتم خود زمانی را که یال e را به جواب اضافه می کنیم در نظر می گیریم ...
یک سری از راس های c در مجموعه ی x هستند و بقیشون تو y ... یالی در درخت t وجود دارد که این دو مجموعه را به هم وصل کرده است ...این یال از یال e کوچکتر است ... در نتیجه تناقض !! ...
پ.ن: یکم فکرم بد نیست ... :-"
برای بدست آوردن یال مینیمم بین دو مجموعه از set استفاده میکنیم , هر یال حداکثر یک بار وارد set و یک بار خارج میشود درنتیجه الگوریتم از اوردر eloge است.
دو الگوریتم بالا هر دو درخت پوشای کمینه (MST) را پیدا می کند ...
اما به نظر من پیاده سازی الگوریتم کروسکال ساده تره .... ولی در کل صَلاح مملکت خویش خسروان دانند ...
درس زندگی : سعی کنید کد های این الگوریتم ها رو یه چند باری بزنید که یه وقت اگه وسط کانتستی, چیزی به دردتون خورد بدون باگ بزنیدشون .... (همه کد هایی که گذاشتیم نه فقط این ۲ تا ... )
