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

بندانگشتی|چپ|600px|پویانمایی توصیف‌کننده الگوریتم بروکا، برای یافتن یک درخت پوشای کمینه - نمونه‌ای از اجرای الگوریتم
**الگوریتم بروکا** الگوریتمی برای پیدا کردن درخت فراگیر مینیمم با وزن یال‌های مجزا در یک گراف است. درخت فراگیر کمینه درختی است شامل تمام رأس‌های یک گراف، به‌طوری‌که مجموع وزن یالهاش کمترین باشد.
این روش برای اولین بار در سال 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 است.
این الگوریتم‌های قطعی و تصادفی مراحل الگوریتم بروکا را تلفیق می‌کنند به این صورت که تعداد مؤلفه‌هایی که برای اتصال باقی می‌ماند را با   مراحل مختلفی که تعداد یال‌های بین جفت مؤلفه‌ها را کاهش می‌دهند، کم می‌کند.
## منابع

رده:الگوریتم‌های گراف
رده:درخت پوشا