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

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

• برای هر گره سبک‌ترین (کم‌وزن‌ترین) یال را انتخاب می‌کنیم.
• یال‌های انتخاب شده از گراف را به درخت مورد نظر اضافه می‌کنیم.

 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.

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

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

در هر تکرار حداقل یک یال از اجزای متصل کم می‌شود و بیشینه تکرار برابر Log V است ( V همان تعداد یال‌هاست)؛ پس مرتبۀ کلی الگوریتم را با توجه به توضیحات می‌توان ${\displaystyle O(ELogV)}$

دیگر الگوریتم‌هایی که برای پیدا کردن درخت فراگیر کمینه وجود دارد الگوریتم پریم و الگوریتم کروسکال است. سریع‌ترین الگوریتم در این زمینه را می‌توان با ترکیب الگوریتم پریم و الگوریتم بروکا به‌دست آورد. سریع‌ترین الگوریتم یافتن درخت پوشای کمینۀ تصادفی بر پایۀ الگوریتم بروکا است که در زمان ${\displaystyle O(E)}$