الگوريتم پرايم براي محاسبه درخت پوشاي کمينه

ورودي اين الگوريتم يک گراف همبند وزن‌دار با مجموعه‌ 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‌ در نظر گرفت، در نتيجه مرتبه اجرايي الگوريتم بالا از مرتبه

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

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