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

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

تحلیل زمانی الگوریتم

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

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

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

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

دیگر الگوریتم‌هایی که برای پیدا کردن درخت فراگیر کمینه وجود دارد الگوریتم پریم و الگوریتم کروسکال است. سریع‌ترین الگوریتم در این زمینه را می‌توان با ترکیب الگوریتم پریم و الگوریتم بروکا به‌دست آورد. سریع‌ترین الگوریتم یافتن درخت پوشای کمینۀ تصادفی بر پایۀ الگوریتم بروکا است که در زمان ${\displaystyle 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 (به چکی و German summary). 3: 37–58.{{cite journal}}: نگهداری یادکرد:زبان ناشناخته (link)
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". Archived from the original on 3 December 2011. Retrieved 2007-02-27.
8. "Minimum Spanning Tree" (PDF). {{cite web}}: Cite has empty unknown parameter: |1= (help)