فصل هرس درخت‌ها رسیده است!

ورودی این الگوریتم یک گراف همبند وزن‌دار با مجموعه‌ V است که شامل رئوس گراف و E (یال‌های گراف) می‌شود.

خروجی الگوریتم یک مجموعه به‌نام Vnew، شامل رئوس درخت حاصل و یک مجموعه Enew‌ (یال‌های درخت) می‌شود. اما این الگوریتم چگونه این کار را می‌کند؟

بگذارید روش کار این الگوریتم را با یک مثال بیان کنیم:

فرض کنیم گرافی داریم با رئوس A، B، C، D، E، F، G و ماتریس مجاورت به‌صورت زیر:

ماتریس مجاورت ماتریسی است که یال‌های یک گراف را نشان می‌دهد. از روی ماتریس مجاورت می‌توان فهمید از یک راس بخصوص تا راس دیگر یالی وجود دارد یا نه؟ و اگر وجود دارد اندازه یال یا همان وزن یال چقدر است؟

بسیار خب، در الگوریتم پرایم یک راس را به‌دلخواه انتخاب می‌کنیم و آن را در مجموعه Vnew قرار می‌دهیم. مثلا راس D، سپس تمامی یال‌های خروجی از D را در می‌آوریم و یالی که کمترین وزن را دارد در نظر می‌گیریم و راس دیگر آن را در Vnew و یال مربوط را در Enew قرار می‌دهیم. برای مثال، یال AD در Vnew قرار می‌گیرد و راس A را نیز به مجموعه Enew می‌افزاییم.

در مرحله بعد باید یال‌هایی را پیدا کنیم که به A یا D نزدیک باشد. در مثال بالا کوتاه‌ترین یالی که در شرط صدق می‌کند، یال DF است. وزن یال AB برابر 7 است، یال DB برابر 9، DE برابر 15 و DF برابر6. پس کوتاه‌ترین یال DF‌ است. این یال در مجموعه Enew ‌قرار می‌گیرد و راس F را در مجموعه Vnew‌ اضافه می‌کنیم.

این کار را آنقدر ادامه می‌دهیم تا تعداد اعضای مجموعه Vnew برابر V شود. چون قرار است درخت پوشا باشد، پس باید شامل تمامی رئوس شود.

از طریق مجموعه Enew نیز می‌توان درخت مورد نظر را رسم کرد.

برای مثال ما درخت پوشای کمینه دارای یال‌های زیر است:

{{A,B},{A,D},{B,E},{C,E},{D,F},{E,G}}

شکل گراف به‌صورت روبه‌روست و یال‌هایی که با رنگ سبز مشخص ‌شده‌اند، نشان‌دهنده درخت پوشای کمینه‌ هستند.

شبه کد الگوریتم پرایم به‌صورت زیر است:

Function prim(m,A)

[Init]

Define nearest[2..n], distance[2..n]

Set F = 0

For i=2 to n

Nearest[i] = 1

Distance[i]=A[1,i]

End-of-for

For j=1 to n-1

Min = Infinity

For i = 2 to n

If 0«=distance[i]«=min

min = distance[i]

vnear=i

end-of-for-i

e=edge connectiong vertices indexed by vnear and nearest[vnear]

add e to F

distance[vnear]=-1

for i=2 to n

if A[1,vnear]«distance[i]

then distance[i] =A[i,vnear]

nearest[i] = vnear

end-of-for-i

end-of-for-j

end

کد منبع این الگوریتم به زبان C را می‌توانید از نشانی زیر دریافت کنید:

اما پیچیدگی زمانی الگوریتم پرایم عمل غالب در الگوریتم بالا مطابق شبه کد حلقه for-j است که دو حلقه تودرتو دارد و عملیات درون آن را می‌توان به‌عنوان عمل غالب در نظر گرفت.

حلقه اصلی که همان for-j است به اندازه n-1 بار تکرار می‌شود. در هر بار تکرار حلقه اصلی، دو حلقه داخلی هر کدام n-1 بار اجرا می‌شوند. اما مدت‌زمان اجرا شدن حلقه for-j‌ از رابطه زیر به‌دست می‌آید:

T(n) = 2(n-1)(n-1)

چون عمل غالب در این الگوریتم حلقه for-j ‌است، می‌توان مدت زمان اجرا شدن الگوریتم را هم‌ارز با مدت‌زمان اجرای حلقه for-j‌ در نظر گرفت، در نتیجه مرتبه اجرایی الگوریتم بالا از مرتبه O(n2)) n2 است.

حال سوال این است که الگوریتم بالا که به روش حریصانه است، درخت پوشای کمینه را درست می‌کند یا نه؟ بهتر است بگوییم درخت حاصل درخت پوشای کمینه است یا نه؟

چون در هر مرحله از اجرای الگوریتم یالی انتخاب می‌شود که کمترین اندازه را داشته باشد، این‌طور به‌نظر می‌رسد که درخت حاصل پوشای کمینه است و جواب الگوریتم درست است اما به هر حال چون روشی که ما در بالا برای نوشتن الگوریتم استفاده کردیم، روش حریصانه است، بهتر است که پس از به‌دست آمدن جواب، صحت بهینه بودن پاسخ بررسی شود.