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

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

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