الگوریتم Borůvka که با نام الگوریتم سولین هم شناخته می‌شود، یک الگوریتم حریصانه است که توسط Otakar Borůvka، ریاضی‌دان اهل کشور چک که بیشتر به‌خاطر فعالیت‌هایش در نظریه گراف شناخته‌شده است، منتشرشده است. مهم‌ترین کاربرد این الگوریتم پیداکردن درخت پوشای کمینه در یک گراف است. در این مقاله ما به بررسی این الگوریتم می‌پردازیم.
مراحل اجرای الگوریتم بروکا و مثال
الگوریتم بروکا یا سولین ساده و شهودی است. بروکا یک الگوریتم حریصانه است که یک راه‌حل "بهینه سراسری" را با استفاده از راه‌حل‌های کوچک‌تر و بهینه محلی برای مسائل فرعی کوچک‌تر می‌سازد. الگوریتم‌های حریصانه معمولاً سعی می‌کنند با برداشتن گام‌های کوچک و با پیداکردن بهینه‌های محلی، درنهایت به بهینه سراسری برسند.
بیایید الگوریتم را به چند مرحله تقسیم کنیم:
- یک گراف همبند، وزن‌دار و بدون جهت را به‌عنوان ورودی بگیرید.
- تمام گره‌ها را به‌عنوان اجزای جداگانه در نظر بگیرید.
- گراف خالی درخت پوشای کمینه (MST) را ایجاد کنید. (این گراف شامل جواب خواهد بود)
- تا زمانی که بیش از یک جزء وجود دارد، عملیات زیر را انجام دهید.
- یال با وزن کمینه را که این جزء را به هر جزء دیگری متصل می‌کند، پیدا کنید.
- در صورتی‌که این یال از قبل در MST وجود ندارد، آن را به MST اضافه کنید.
- اگر تنها یک جزء باقی‌مانده است، درخت پوشای کمینه را برگردانید.
حال بیایید در گراف زیر و با استفاده از الگوریتم بروکا، درخت پوشای کمینه را پیدا کنیم:
در گراف بدون جهت بالا، 9 رأس داریم. حال بیایید جدول زیر را برای توزیع وزنی ببینیم.
| اجزا | کم وزن ترین یالی که آن را به جزء دیگر متصل می کند | وزن یال |
|---|---|---|
| {0} | 0-1 | 4 |
| {1} | 0-1 | 4 |
| {2} | 2-4 | 2 |
| {3} | 3-5 | 5 |
| {4} | 4-7 | 1 |
| {5} | 3-5 | 10 |
| {6} | 6-7 | 1 |
| {7} | 4-7 | 1 |
| {8} | 7-8 | 3 |
پس از متصل‌کردن این اجزا گراف به شکل زیر خواهد بود. (یال‌های سبزرنگ، یال‌هایی هستند که در درخت پوشای کمینه خواهند بود)
همان‌طور که می‌بینیم، اکنون اجزای زیر را داریم: {0، 1}، {2، 4، 6، 7، 8} و {3، 5}. دوباره، الگوریتم را برای یافتن یال‌های با وزن حداقل اعمال می‌کنیم.
| اجزا | کم وزن ترین یالی که آن را به جزء دیگر متصل می کند | وزن یال |
|---|---|---|
| {0, 1} | 0-6 | 7 |
| {2, 4, 6, 7, 8} | 2-3 | 6 |
| {3, 5} | 2-3 | 6 |
پس از این مرحله، گراف ما به شکل زیر خواهد بود:
همان‌طور که مشاهده می‌کنیم، تنها یک جزء در گراف وجود دارد که نشان‌دهنده درخت پوشای کمینه است. وزن این درخت 29 است که پس از جمع تمام یال‌ها به آن می‌رسیم؛ بنابراین ما عملکرد الگوریتم Boruvka را دیدیم. حالا این الگوریتم را با استفاده از زبان پایتون و سی پلاس پلاس پیاده‌سازی می‌کنیم.
پیاده سازی الگوریتم بروکا
Python
# Boruvka’s algorithm to find Minimum Spanning
# Tree of a given connected, undirected and weighted graph
from collections import defaultdict
#Class to represent a graph
class Graph:
def __init__(self,vertices):
self.V= vertices #No. of vertices
self.graph = [] # default dictionary to store graph
# function to add an edge to graph
def addEdge(self,u,v,w):
self.graph.append([u,v,w])
# A utility function to find set of an element i
# (uses path compression technique)
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
# A function that does union of two sets of x and y
# (uses union by rank)
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
# Attach smaller rank tree under root of high rank tree
# (Union by Rank)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
#If ranks are same, then make one as root and increment
# its rank by one
else :
parent[yroot] = xroot
rank[xroot] += 1
# The main function to construct MST using Kruskal’s algorithm
def boruvkaMST(self):
parent = []; rank = [];
# An array to store index of the cheapest edge of
# subset. It store [u,v,w] for each component
cheapest =[]
# Initially there are V different trees.
# Finally there will be one tree that will be MST
numTrees = self.V
MSTweight = 0
# Create V subsets with single elements
for node in range(self.V):
parent.append(node)
rank.append(0)
cheapest =[-1] * self.V
# Keep combining components (or sets) until all
# components are not combined into single MST
while numTrees > 1:
# Traverse through all edges and update
# cheapest of every component
for I in range(len(self.graph)):
# Find components (or sets) of two corners
# of current edge
u,v,w = self.graph[i]
set1 = self.find(parent, u)
set2 = self.find(parent ,v)
# If two corners of current edge belong to
# same set, ignore current edge. Else check if
# current edge is closer to previous
# cheapest edges of set1 and set2
if set1 != set2:
if cheapest[set1] == -1 or cheapest[set1][2] > w :
cheapest[set1] = [u,v,w]
if cheapest[set2] == -1 or cheapest[set2][2] > w :
cheapest[set2] = [u,v,w]
# Consider the above picked cheapest edges and add them
# to MST
for node in range(self.V):
#Check if cheapest for current set exists
if cheapest[node] != -1:
u,v,w = cheapest[node]
set1 = self.find(parent, u)
set2 = self.find(parent ,v)
if set1 != set2 :
MSTweight += w
self.union(parent, rank, set1, set2)
print (“Edge %d-%d with weight %d included in MST” % (u,v,w))
numTrees = numTrees – 1
#reset cheapest array
cheapest =[-1] * self.V
print (“Weight of MST is %d” % MSTweight)
g = Graph(4)
g.addEdge(0, 1, 10)
g.addEdge(0, 2, 6)
g.addEdge(0, 3, 5)
g.addEdge(1, 3, 15)
g.addEdge(2, 3, 4)
g.boruvkaMST()
++C
// Boruvka’s algorithm to find Minimum Spanning
// Tree of a given connected, undirected and weighted graph
#include <bits/stdc++.h>
using namespace std;
// Class to represent a graph
class Graph {
int V; // No. of vertices
vectorvector >graph; // default dictionary to store graph
// A utility function to find set of an element i
// (uses path compression technique)
int find(vector& parent, int i)
{
if (parent[i] == i) {
return I;
}
return find(parent, parent[i]);
}
// A function that does union of two sets of x and y
// (uses union by rank)
void unionSet(vector<int>& parent, vector<int>& rank,
int x, int y)
{
int xroot = find(parent, x);
int yroot = find(parent, y);
// Attach smaller rank tree under root of high rank
// tree (Union by Rank)
if (rank[xroot] rank[yroot]) {
parent[xroot] = yroot;
}
else if (rank[xroot] > rank[yroot]) {
parent[yroot] = xroot;
}
// If ranks are same, then make one as root and
// increment its rank by one
else {
parent[yroot] = xroot;
rank[xroot]++;
}
}
public:
Graph(int vertices)
{
V = vertices;
graph = vectorvector >();
}
// function to add an edge to graph
void addEdge(int u, int v, int w)
{
graph.push_back({ u, v, w });
}
// The main function to construct MST using Kruskal’s
// algorithm
void boruvkaMST()
{
vector parent(V);
// An array to store index of the cheapest edge of
// subset. It store [u,v,w] for each component
vector rank(V);
vectorvector > cheapest(V,
vector(3, -1));
// Initially there are V different trees.
// Finally there will be one tree that will be MST
int numTrees = V;
int MSTweight = 0;
// Create V subsets with single elements
for (int node = 0; node V; node++) {
parent[node] = node;
rank[node] = 0;
}
// Keep combining components (or sets) until all
// components are not combined into single MST
while (numTrees > 1) {
// Traverse through all edges and update
// cheapest of every component
for (int I = 0; I w) {
cheapest[set1] = { u, v, w };
}
if (cheapest[set2][2] == -1
|| cheapest[set2][2] > w) {
cheapest[set2] = { u, v, w };
}
}
}
// Consider the above picked cheapest edges and
// add them to MST
for (int node = 0; node < V; node++) {
// Check if cheapest for current set exists
if (cheapest[node][2] != -1) {
int u = cheapest[node][0],
v = cheapest[node][1],
w = cheapest[node][2];
int set1 = find(parent, u),
set2 = find(parent, v);
if (set1 != set2) {
MSTweight += w;
unionSet(parent, rank, set1, set2);
printf(“Edge %d-%d with weight %d “
“included in MST\n”,
u, v, w);
numTrees--;
}
}
}
for (int node = 0; node < V; node++) {
// reset cheapest array
cheapest[node][2] = -1;
}
}
printf(“Weight of MST is %d\n”, MSTweight);
}
};
int main()
{
Graph g(4);
g.addEdge(0, 1, 10);
g.addEdge(0, 2, 6);
g.addEdge(0, 3, 5);
g.addEdge(1, 3, 15);
g.addEdge(2, 3, 4);
g.boruvkaMST();
}
مقایسه با الگوریتم های مشابه
مقایسه با الگوریتم کروسکال
در الگوریتم کروسکال، اول‌ازهمه می‌خواهیم تمام یال‌ها را از سبک‌ترین به سنگین‌ترین آن‌ها مرتب کنیم. سپس در هر مرحله یال با کمترین یال را حذف می‌کنیم و اگر یک دور در درخت ما ایجاد نمی‌کند (که در ابتدا از V| - 1| رأس جداگانه تشکیل شده است) آن را به MST اضافه می‌کنیم. در غیر این صورت فقط آن را حذف می‌کنیم.
الگوریتم Boruvka به دنبال نزدیک‌ترین همسایه هر جزء (در ابتدای رأس) است. همچنان کم‌وزن‌ترین یال را از هر جزء انتخاب می‌کند و آن را به MST ما اضافه می‌کند. وقتی فقط یک جزء متصل داشته باشیم، کار تمام است.
مقایسه با الگوریتم پریم
الگوریتم پریم ماهیت ترتیبی دارد. MST را در هر مرحله با گرفتن کم‌وزن‌ترین یال که دقیقاً یک انتهای آن در قسمت ازقبل ساخته‌شده MST دارد، یک رأس افزایش می‌دهد.
الگوریتم Borůvka ماهیت موازی دارد (و درواقع پایه‌ای برای الگوریتم‌های MST موازی کارآمد است). در هر مرحله، کم‌وزن‌ترین یال را از هر رأس انتخاب می‌کند، همه آن‌ها را به‌یک‌باره به MST اضافه می‌کند و هر جزء متصل را به یک جزء متصل دیگر وصل می‌کند.
مزیت الگوریتم بروکا
مزیت قابل‌توجه الگوریتم Boruvka یا سولین این است که به‌راحتی می‌توان آن را به‌صورت موازی پیاده کرد، زیرا انتخاب کم‌وزن‌ترین یال خروجی برای هر جزء کاملاً مستقل از انتخاب‌های انجام‌شده توسط اجزای دیگر است.
کاربردهای الگوریتم بروکا
مهم‌ترین کاربرد این الگوریتم پیداکردن درخت پوشای کمینه یک گراف است.
جمع‌بندی
بسیاری از الگوریتم‌های درخت پوشای کمینه محبوب دیگر مانند الگوریتم Prim یا Kruskal وجود دارد. بااین‌حال، الگوریتم Boruvka یا سولین، یک الگوریتم متفاوت نیست و تقریباً همان نتیجه را می‌دهد. همه این الگوریتم‌ها درخت پوشای کمینه را پیدا می‌کنند و پیچیدگی زمانی تقریباً یکسانی دارند. الگوریتم Boruvka مزایای بیشتری نسبت به سایر الگوریتم‌ها دارد. برای یافتن درخت پوشای کمینه نیازی به از پیش مرتب‌کردن یال‌ها یا حفظ صف اولویت ندارد. در این مقاله، الگوریتم Boruvka، مثال آن و پیاده‌سازی آن را مورد بررسی قرار دادیم.
آیا الگوریتم بروکا یک الگوریتم حریصانه است؟
الگوریتم Boruvka نیز مانند Prim و Kruskal یک الگوریتم حریصانه است.
کاربرد الگوریتم بروکا چیست؟
مهم‌ترین کاربرد این الگوریتم پیداکردن درخت پوشای کمینه یک گراف است.
مزیت الگوریتم بروکا نسبت به سایر الگوریتم های مشابه چیست؟
مزیت قابل‌توجه الگوریتم Boruvka این است که به‌راحتی می‌توان آن را به‌صورت موازی پیاده کرد، زیرا انتخاب کم‌وزن‌ترین یال خروجی برای هر جزء کاملاً مستقل از انتخاب‌های انجام‌شده توسط اجزای دیگر است.
مطالب مرتبط
همه مقالات
