توصیه : فک کنم اون کدی هایی رو که گذاشتیم رو باز کنید و باهاش مطالب زیر رو بخونید بهتر باشه .... (کد ها)
دایکسترا : واسه پیش زمینه بهتون پیشنهاد میکنم یه سری به این لینک بزنین که با الگوریتم و هدفش آشنا شید ...
الگوریتم رو بر حسب کدی که تو پستای قبلی گذاشتیم شرح و سپس نوع زدنش رو متذکز میشیم !
هدف ما پیدا کردن مینیمم فاصله ی یک راس تا بقیه راس هاست ... (راس مورد نظر را Start مینامیم)
ابتدا فاصله بقیه رئوس تا Start را برابر بی نهایت قرار داده ... و همه ی رئوس به غیر از Start را در یک مجموعه در نظر میگیریم ... (مجموعه ی مورد نظر را S مینامیم)
سپس در هر مرحله بین اعضای S آن راسی را که کوچکترین فاصله تا Start را دارد را از S حذف کرده و سپس بقیه روئس را به روز (update) می کنیم.
برای پیدا کردن مینیمم, فواصل را در Set نگهداری میکنیم ...
منظور از update بقیه روئس تغییر دادن فاصله ی روئسی که در S باقی مانده اند تا راس Start است ...... (راس حذف شده را i مینامیم)
اثبات می شود که راسی که آن را حذف می کنیم دیگر update نمی شود و فاصله آن تا Start ثابت میماند .... (اثبات بر عهده ی خواننده ... راهنمایی : استقرا +برهان خلف)
برای update بقیه روئس بر روی همسایه های i حرکت میکنیم ....
سپس فاصله آن ها تا راس S را برابر مینیمم [فاصله فعلی آن ها] با[ (فاصله ی i تا S ) + اندازه ی یال بین i و همسایه اش] قرار می دهیم ....
در کد قرار داده شده در آرایه Dis فاصله روئس تا S را نگه داری می کنیم ... در وکتور v گراف را ... و در سِت s مجموعه ی S را ....
پیچیدگی : با استفاده از set هر عمل از اُردر logn است و در مجموع برای هر راس یک بار بر روی همسایه هایش حرکت می کنیم که میشه از اُردر e )
درنتیجه (nlogn * ماکسیمم درجات) عمل انجام می دهیم که می شه از اُردر n^2 * logn یا همون elogn.
امیدوارم فهمیده باشین ...
LIS : پیدا کردن بزرگترین زیر دنباله صعودی .... اینم یه لینک واسه داشتن پیش زمینه ...
تعریف [Dp[i : در بین عضو های i_ام دنباله های صعودی به طول i مینیمم را در [Dp[i نگه داری میکنیم ....
ُSize برابر است با ماکسیمم دنباله ی صعودی که تا کنون یافته ایم ....
حال به ترتیب بر روی دنباله شروع به حرکت میکنیم اگر عدد فعلی از [Dp[Size بیشتر بود [Dp[1+Size را برابر عد فعلی قرار می دهیم ...
در غیر این صورت بین بازه ی 1 تا Size اولین جایی را که Dp آن بزرگتر از عدد فعلی است را برابر عدد فعلی قرار می دهیم .... (update_DP)
این کار رو میشه با یه باینری سرچ و از order لاگ n انجام داد چون اعداد تو خونه های Dp به صورت sort شده هستند ...
پیچیدگی : این الگوریتم از اُردر nlogn است زیرا در هر مرحله واسه بررسی عدد جدید حداکثر logn عمل انجام می دهد ....(باینری سرچ از اُردر logn است)
اثبات درستی الگوریتم و فهمیدن مطالب فهمیده نشده بر عهده ی خواننده !!
Bfs & Dfs : از این لینک مطالعه فرمایید!
پیدا کردن راس برشی : این کار را با یک Dfs انجام می دهیم ....
تعریف [H[i : ارتفاع راس i_اُم.
تعریف [Dp[i : بالا ترین راسی که زیر درخت i به آن متصل است ... (بالاترین راس یعنی راسی که مینیمم ارتفاع را دارد)
تعریق [C[i : تعداد راس هایی که راس i_اُم باعث mark شدن آن ها می شود ... (کل همسایه هاش منهای اونایی که قبلا mark شدن(از همسایه هاش!)!)!
نحوه ی update شدن Dp برای راس p : (استقرا) فرض می کنیم واسه ی زیر درخت راس مورد نظر Dp ها درست هستند ....
حالا فقط باس بین اونا و همسایه هایه p که قبلا mark شدن .... مینیمم رو مساوی Dp راس مورد نظر گذاشت ....
اگر راسی مثل q وجود داشت که بین Dp بچه هایش هیچ کدام از H راس q کوچکتر نبود و C راس q بزرگتر از 0 بود q راسی برشی خواهد بود .... (اثبات بر عهده ی خواننده)
برای راسی که از روی آن Dfs زده ایم شرایط فرق میکنه و اگر تعداد بچه های اون راس از 1 بیشتر باشه راس اِه برشی اِه .... (اثبات از روی تعریف Dfs)
پیچیدگی : برای هر راس روی همسایه هایش حرکی می کنیم پس جواب برابر زیگما (d(i است که می شود 2 * تعداد یال ها ....
امیدواریم به درتون بخوره !