درخت پوشای کمینه

درخت پوشای کمینه یا درخت فراگیر مینیمم در گراف‌های ارزش دار (وزن دار) ساخته می‌شود.

فرض کنید گراف یک گراف همبند باشد (یعنی بین هردو رأس متمایز آن یک مسیر وجود داشته باشد) منظور از یک درخت پوشا از این گراف درختی است که شامل همه رئوس این گراف باشد ولی فقط بعضی از یال‌های آنرا دربر گیرد. منظور از درخت پوشای مینیمم (برای گراف همبند وزن دار) درختی است که بین درخت‌های پوشای آن گراف، مجموع وزن یال‌های آن، کمترین مقدار ممکن باشد.برای به دست آوردن درخت پوشای بهینه یک گراف جهت دار متصل می توان از الگوریتم‌های متفاوتی استفاده نمود.سه الگوریتم معروف پیدا کردن درخت پوشای کمینه عبارتند از : الگوریتم کروسکال الگوریتم پریم الگوریتم سولین

الگوریتم کروسکال

در الگوریتم کراسکال یال‌های گراف را به ترتیب صعودی مرتب می کنیم. از اولین (کوچکترین) یال شروع کرده و هر یال را به گراف اضافه می کنیم به شرط اینکه دور در گراف ایجاد نگردد. این روال را آنقدر ادامه می دهیم تا درخت پوشای بهینه تشکیل گردد.

این الگوزیتم نیزمشابه الگوریتم پریم برای یافتن درخت پوشای کمینه ی یک گراف به کارمی رود.دراین الگوریتم ابتدایال هاازکمترین وزن به بیشترین وزن مرتب می گردندسپس یال هابه ترتیب انتخاب شده واگریالی ایجادحلقه کندوکنارگذاشته می شود.عملیات هنگامی خاتمه می یابدکه تمام رأس هابه هم وصل شوندیااینکه تعدادیال های موجوددرF برابرn-1 شودکه n تعدادرأس ها است.که دربعضی کتابها بانام راشال مطرح شده است.شکل زیر مراحل کاررابرای یک گراف فرضی نشان می دهد.

بیشترزمان درالگوریتم کروسکال مربوط به مرتب سازی یالهاست.پس اگرتعدادیال e باشدزمان این الگوریتم ازمرتبه (e lg e) Ѳ خواهدبود.

نکته : اگرe نزدیک به کران پایین باشدیعنی گراف نسبتاخلوت بوده ویال کمی داشته است.الگوریتم کروسکال ازمرتبه روبه رو است :

(n lg n) Ѳ = (e lg e) Ѳ

واگرe نزدیک به کران بالا باشد یعنی گراف نسبتاپرباشدویالهای زیادی داشته باشد:

(n2 lg n) Ѳ      =   (n2.2 lg n) Ѳ      =   (n2 lg n2) Ѳ      = (e lg e) Ѳ 

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

 1  function Kruskal(G)
 2    for each vertex v in G do
 3      Define an elementary cluster C(v) ← {v}.
 4    Initialize a priority queue Q to contain all edges in G, using the weights as keys.
 5    Define a tree T ← Ø       //T will ultimately contain the edges of the MST
 6     // n is total number of vertices
 7    while T has fewer than n-1 edges do
 8      // edge u,v is the minimum weighted route from/to v
 9      (u,v) ← Q.removeMin()
10      // prevent cycles in T. add u,v only if T does not already contain a path between u and v. 
11      // Note that the cluster contains more than one vertex only if an edge containing a pair of
12      // the vertices has been added to the tree.
13      Let C(v) be the cluster containing v, and let C(u) be the cluster containing u.
14      if C(v) ≠ C(u) then
15        Add edge (v,u) to T.
16        Merge C(v) and C(u) into one cluster, that is, union C(v) and C(u).
17    return tree T

نحوهٔ کار الگوریتم کراسکال به این صورت است که یک جنگل از درخت هارا به ترتیب با هم ادغام می‌کند تا به یک درخت واحد برسد. در اینجا نمونه‌ای از چگونگی عملکرد الگوریتم کراسکال آورده‌ایم:

الگوریتم پریم

در این روش از یک رأس شروع می کنیم و کمترین یال (یال با کمترین وزن) که از آن می گذرد را انتخاب می کنیم. در مرحله بعد یالی انتخاب می‌شود که کمترین وزن را در بین یال‌هایی که از دو گره موجود می گذرد داشته باشیم. به همین ترتیب در مرحله بعد یالی انتخاب می‌گردد که کمترین وزن را در بین یالهایی که از سه گره موجود می گذرد داشته باشد. این روال را آنقدر تکرار می کنیم تا درخت پوشای بهینه حاصل شود. باید توجه کرد که یال انتخابی در هر مرحله در صورتی انتخاب می‌شود که در گراف دور ایجاد نکند. تفاوت روش پریم با روش کراسکال در این است که گراف حاصل در مراحل میانی تشکیل درخت پوشای بهینه در روش پریم همیشه متصل است ولی در الگوریتم کراسکال در آخرین مرحله قطعاً متصل است.

while latest_addition = remove minimum in Q
    set is_in_Q of latest_addition to false
    add latest_addition to (minimum_adjacency_list of (parent of latest_addition))
    add (parent of latest_addition) to (minimum_adjacency_list of latest_addition)
 for each adjacent of latest_addition
    if (is_in_Q of adjacent) and (weight-function(latest_addition, adjacent) <min_distance of adjacent)
        set parent of adjacent to latest_addition
        set min_distance of adjacent to weight-function(latest_addition, adjacent)
update adjacent in Q, order by min_distance

• ممکن است درختهایی که الگوریتم مذکور تولید می‌کنند، از لحاظ شکل ظاهری متفاوت باشند، ولی وزن همهٔ درخت‌ها یکسان است.
• مرتبهٔ زمانی الگوریتم پریم برابر (o(n^2 است. (حلقهٔ while، برای n دفعه و عمل یافتن از میان لبه‌های متصل به یک مجموعه دور خاص n دفعه اتفاق می افتد؛ که در مجموع برابر n^2 دفعه می‌شود).

زمان اجرای الگوریتم prim

به چگونگی پیاده سازی صف اولویت Q بستگی دارد. اگر Q به صورت min-heap دودویی پیاده‌سازی شود. می‌توانیم از روال BUILD-MIN-HEAP در خطوط ۵-۱ برای مقدار دهی اولیه در زمان(O(V استفاده کنیم. بدنه حلقهwhile، |V| بار اجرا می‌شود. و چون هر عمل EXTRACT-MIN زمان(O(lgV را صرف می‌کند زمان کل برای همه فراخوانی EXTRA-MIN برابر(O(vlogV است. حلقه for در خطوط ۱۱-۸ روی هم رفته (O(E بار اجرا می‌شود چون مجموعه طول همه لیست‌های همجواری برابر ۲|E| می‌باشد. در داخل حلقه for بررسی برای عضویت در Q در خط ۹ می‌تواند در زمان ثابت با نگهداری یک بیت برای هر راس که بیان می‌کند آیا آن راس در Q قرار دارد یا خیر، پیاده سازی می‌شود و وقتی که راس از Q حذف شود بروز رسانی بیت انجام می‌گیرید. انتساب در خط۱۱ شامل یک عمل DECREASE- KEY ضمنی بر روی min-heap است که می‌تواند در min-heap دودویی در زمان(O(lgV پیاده‌سازی شود. بنابراین زمان کل برای الگوریتم Prim برابر(O(VlgV+ ElgV)= O(ElgV است که به طور مجانبی با پیاده‌سازی الگوریتم Kruskal یکسان می‌باشد. اگر heap فیبوناچی برای پیاده سازی صف اولویت مینیمم Q استفاده شود. زمان اجرای الگوریتم Prim به(O(E+VlgV بهبود می‌یابد.

الگوریتم سولین

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

منابع

• [۱]
• [۲]
• [۳]
• [۴]