میخواستم یکی لگوریتم پریم که با ماتریس مجاورت پیاده سازی میشه رو توضیح بده !
میدونم این الگوریتم یه ماتریس از وزن های کم تولید میکنه .......
میخوام که الگوریتم به زبان الگوریتمی(for i=2 to n do nearest[i=1]) نوشته بشه و گفته شه که دفیفا هر خط تو کدوم مرحله است؟
دوستان میتونند کمکم کنند؟؟
کد:
function Prim(L[1..n,1..n]):set of edges
۱/ {initialization: only node 1 is in B}
۲/T <-- {will contain the edges of the minimum spanning tree}
۳/ for i=2 to n do
۴/ nearest[i] <-- 1
۵/ mindist[i] <--L[i,1]
۶/ {greedy loop}
۷/ repeat n-1 times
۸/ min <-- INF
۹/ for j <-- 2 to n do
۱۰/ if 0 mindist[j] < min Then
۱۱/ min <-- mindist[j]
۱۲/ k <-- j
۱۳/ T=T [ {nearest[k],k}
۱۴/ mindist[k] <-- -1{add k to B}
۱۵/ for j <-- 2 to n do
۱۶/ if L[j,k] < mindist[j] Then
۱۷/ mindist[j] <-- L[j,k]
۱۸/ nearest[j] <-- k Return Tکلاً الگوریتمش این طوریه که توی هر مرحله یه سری راس مارک شده داره و یه سری راس مارک نشده و توی هر مرحله کوتاهترین یالی که یک راس مارک نشده را به یک راس مارک شده وصل میکند پیدا کرده و به مجموعه‌ی یال های انتخاب شده می افزاییم آن سر دیگرش را مارک میکنیم و سایر راس‌ها را update میکنیم.
از راس شماره یک شروع میکنیم و اون رو مارک میکنیم، بعد چون تنها راس مارک شده راس ۱ هست، پس تنها یالی که بین هر راس با یک راس مارک نشده می تواند وجود داشته باشد، تا همین راس ۱ است پس در خط ۴ و ۵ نزدیکترین راس مارک شده به هر کس را راس ۱ قرار میدهد.
[mindist[j، اگر j مارک نشده باشد کمترین فاصله ای که بین j و یکی از راس های مارک شده تا کنون پیدا شده است را نگه میدارد (فاصله اش تا نزدیکترین راس مارک شده) و اگر j مارک شده باشد مقدار ۱- دارد
[nearest[j اندیس نزدیکترین راس مارک شده به j را نگه میدارد
از خط ۹ تا خط ۱۲ کوچکترین یالی که یک سر آن مارک شده و یک سر آن مارک نشده را می یابد (k سر مارک نشده‌ی این یال است) و در خط ۱۳ این یال را به مجموعه یال هایی که تا کنون انتخاب شده می افزاید و در خط ۱۴ راس k را مارک میکند.
از خط ۱۵ تا ۱۷ بررسی میکند که اگر فاصله‌ی j تا راسی که جدیداً مارک شده کمتر از فاصله اش تا یال های مارک شده‌ی قبلی بود، مقدارش را به فاصله‌ی جدید تغییر میدهد.
این کار را آن قدر تکرار میکند تا همه‌ی راس‌ها مارک شوند.