درخت پوشای کمینه: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز ویرایش به وسیلهٔ ابزار خودکار ابرابزار |
بدون خلاصۀ ویرایش |
||
خط ۱:
'''درخت پوشای کمینه''' یا درخت فراگیر مینیمم در [[گراف|گراف‌های]] ارزش دار (وزن دار) ساخته می‌شود.
فرض کنید گراف یک گراف همبند باشد (یعنی بین هردو رأس متمایز آن یک مسیر وجود داشته باشد) منظور از یک درخت پوشا از این گراف درختی است که شامل همه رئوس این گراف باشد ولی فقط بعضی از یالهای آنرا دربر گیرد. منظور از درخت پوشای مینیمم (برای گراف همبند وزن دار) درختی است که بین درخت‌های پوشای آن گراف، مجموع وزن یالهای آن، کمترین مقدار ممکن باشد.
[[الگوریتم کروسکال]]
[[الگوریتم پریم]]
خط ۷:
== الگوریتم کروسکال ==
در الگوریتم کراسکال یالهای گراف را به ترتیب صعودی مرتب
این الگوزیتم نیزمشابه الگوریتم پریم برای یافتن درخت پوشای
بیشترزمان درالگوریتم کروسکال مربوط به مرتب سازی یالهاست.
نکته : اگرe نزدیک به کران پایین باشدیعنی گراف نسبتاخلوت بوده ویال کمی داشته است.
(n lg n) Ѳ = (e lg e) Ѳ
خط ۱۹:
واگرe نزدیک به کران بالا باشد یعنی گراف نسبتاپرباشدویالهای زیادی داشته باشد:
(n2 lg n) Ѳ = (n2.2 lg n) Ѳ = (n2 lg n2) Ѳ = (e lg e) Ѳ
پس اگرگرافی یالهای کمی داردبهتراست ازروش کروسکال واگریالهای زیادی دارد بهتراست ازروش پریم استفاده کنیم.
{{چپ‌چین}}
<source lang=
1 function Kruskal(G)
2 for each vertex v in G 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.
خط ۴۸:
== الگوریتم پریم ==
در این روش از یک رأس شروع
{{چپ‌چین}}
<source lang=
while latest_addition = remove minimum in Q
set is_in_Q of latest_addition to false
خط ۶۳:
{{پایان چپ‌چین}}
* ممکن است درختهایی که الگوریتم مذکور تولید می‌کنند، از لحاظ شکل ظاهری متفاوت باشند، ولی وزن همهٔ درخت‌ها یکسان است.
* مرتبهٔ زمانی الگوریتم پریم برابر (o(n^2 است. (حلقهٔ while، برای n دفعه و عمل یافتن از میان لبه‌های متصل به یک مجموعه دور خاص n دفعه اتفاق
== زمان اجرای الگوریتم 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 بهبود می‌یابد.
== الگوریتم سولین ==
در الگوریتم سولین برای هر گره یال با کمترین هزینه که از آن عبور می‌کند را رسم
== منابع ==
| |||