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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
پویانمایی توصیف‌کننده الگوریتم بروکا، برای یافتن یک درخت پوشای کمینه - نمونه‌ای از اجرای الگوریتم

الگوریتم بروکا الگوریتمی برای پیدا کردن درخت فراگیر مینیمم با وزن یال‌های مجزا در یک گراف است. درخت فراگیر کمینه درختی است شامل تمام راس‌های یک گراف، به طوری‌که مجموع وزن یالهاش کمترین باشد.
این روش برای اولین بار در سال 1926 توسط اوتاکار بروکا به عنوان یک روش ساخت شبکه‌ی توزیع انرژی الکتریکی کارآمد برای موراوی منتشر شده است.[۱][۲] [۳] الگوریتم در سال 1938 توسط Choquet و در سال 1950 توسط Florek و Łukasiewicz و Perkal و Zubrzycki Steinhaus و برای بار دیگر در سال 1965 توسط Sollin دوباره کشف شد. [۴] [۵] [۶] از آن‌جایی که سولین تنها دانشمندی از این لیست بوده که در کشورهای انگلیسی زبان زندگی می‌کرده، این الگوریتم غالباً و به‌خصوص در پردازش موازی به الگوریتم سولین مشهور است.

شرح الگوریتم[ویرایش]

الگوریتم بروکا را می توان حالت موازی الگوریتم پریم دانست.
در هر راس گراف، سبک‌ترین یال را انتخاب می‌کنیم و راس انتهایی یال انتخاب شده را نیز علامت می‌زنیم و این دو راس را از گراف حذف می‌کنیم و این کار را ادامه می‌دهیم تا گراف به یک راس تبدیل شود؛ درخت کمینه‌ی مورد نظر ما درختی متشکل از راس‌ها و یال‌های انتخاب شده است.
مراحل الگوریتم: روش زیر را تا وقتی گراف به یک گره تبدیل شود ادامه می‌دهیم:

  • برای هر گره سبک‌ترین (کم‌وزن‌ترین) یال را انتخاب می‌کنیم.
  • یال‌های انتخاب شده از گراف را به درخت مورد نظر اضافه می‌کنیم.
 1 Begin with a connected graph G containing edges of distinct weights, and an empty set of edges T
 2 While the vertices of G connected by T are disjoint:
 3   Begin with an empty set of edges E
 4   For each component:
 5     Begin with an empty set of edges S
 6     For each vertex in the component:
 7       Add the cheapest edge from the vertex in the component to another vertex in a disjoint component to S
 8     Add the cheapest edge in S to E
 9   Add the resulting set of edges E to T.
10 The resulting set of edges T is the minimum spanning tree of G.

تحلیل زمانی الگوریتم[ویرایش]

در هر تکرار حلقه باید موارد زیر محاسبه شود:

  • در گام اول باید برای هر راس یال مورد نظر را پیدا کرد که این کار بدون نیاز به مرتب کردن یال‌ها در زمان O(E) انجام می‌شود.(E برابر تعداد راس‌هاست.)
  • در گام بعد با پیدا شدن یال‌های مورد نظر باید راس‌ها را دوباره علامت‎گذاری کرد که این کار را نیز می‌توان به کمک الگوریتم جستجوی عمق اول در زمان O(E) انجام داد.


در هر تکرار حداقل یک یال از اجزای متصل کم می‌شود و بیشینه تکرار برابر Log V است ( V همان تعداد یال‌هاست)؛ پس مرتبه‌ی کلی الگوریتم را با توجه به توضیحات می‌توان O(E Log V) درنظر گرفت.[۷][۸]

الگوریتم‌های مشابه[ویرایش]

دیگر الگوریتم‌هایی که برای پیدا کردن درخت فراگیر کمینه وجود دارد الگوریتم پریم و الگوریتم کروسکال است. سریع‌ترین الگوریتم در این زمینه را می‌توان با ترکیب الگوریتم پریم و الگوریتم بروکا به‌دست آورد. سریع‌ترین الگوریتم یافتن درخت پوشای کمینه‌ی تصادفی بر پایه‌ی الگوریتم بروکا است که در زمان O(E) اجرا می‌شود؛ بهترین الگوریتم قطعی شناخته شده برای یافتن درخت کمینه‌ی پوشا ( که توسط Bernard Chazelle معرفی شد) نیز برپایه‌ی الگوریتم بروکا و با زمان اجرایی برابر ((O(E α(V است.
این الگوریتم‌های قطعی و تصادفی مراحل الگوریتم بروکا را تلفیق می‌کنند به این صورت که تعداد مولفه هایی که برای اتصال باقی می‌ماند را با مراحل مختلفی که تعداد یال‌های بین جفت مولفه‌ها را کاهش می‌دهند، کم می‌کند.

منابع[ویرایش]

  1. Borůvka, Otakar (1926). "O jistém problému minimálním (About a certain minimal problem)". Práce mor. přírodověd. spol. v Brně III 3: 37–58. 
  2. Borůvka, Otakar (1926). "Příspěvek k řešení otázky ekonomické stavby elektrovodních sítí (Contribution to the solution of a problem of economical construction of electrical networks)". Elektronický Obzor 15: 153–154. 
  3. "Nesetril and Milkova and Nesetrilova" (2001). "Otakar Boruvka on Minimum Spanning Tree Problem: Translation of Both the 1926 Papers, Comments, History". DMATH: Discrete Mathematics 233. 
  4. Choquet, Gustave (1938). "Étude de certains réseaux de routes". Comptes-rendus de l’Académie des Sciences 206: 310–313. 
  5. Florek, Kazimierz (1951). "Sur la liaison et la division des points d'un ensemble fini". Colloquium Mathematicum 2 (1951) : 282–285. 
  6. Sollin, M. (1965). "Le tracé de canalisation". Programming, Games, and Transportation Networks . 
  7. "Boruvka's MST algorithm". Retrieved 2007-02-27. 
  8. "Minimum Spanning Tree".