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

دانشنامه عمومی

الگوریتم بروکا الگوریتمی برای پیدا کردن درخت فراگیر مینیمم با وزن یال های مجزا در یک گراف است. درخت فراگیر کمینه درختی است شامل تمام رأس های یک گراف، به طوری که مجموع وزن یالهاش کمترین باشد. این روش برای اولین بار در سال 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 ) {\displaystyle O ( E ) } انجام می شود. ( E برابر تعداد یال هاست. )
• در گام بعد با پیدا شدن یال های مورد نظر باید رأس ها را دوباره علامت گذاری کرد که این کار را نیز می توان به کمک الگوریتم جستجوی عمق اول در زمان O ( E ) {\displaystyle O ( E ) } انجام داد.
عکس الگوریتم بروکاعکس الگوریتم بروکا
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلف

پیشنهاد کاربران

بپرس