A Borůvka-algoritmus (más néven Borůvka-féle algoritmus) egy hatékony módszer, amely minimális feszítőfát (MST - Minimum Spanning Tree) épít egy súlyozott, összefüggő gráfban. Ez az algoritmus iteratív módon működik, és az összes csúcsot egy-egy komponensként kezeli, majd minden iterációban a legkisebb súlyú éleket adja hozzá, amelyek különböző komponenseket kötnek össze.
Az algoritmus a következő módon működik: 1. Kezdetben minden csúcs külön komponens. 2. Iteratívan: - Minden komponens kiválasztja a legkisebb súlyú élt, amely egy másik komponenshez vezet. - Ezek az élek hozzáadódnak a minimális feszítőfához. - Az összekapcsolt komponensek egyesülnek. 3. Végül: Az algoritmus addig folytatódik, amíg csak egyetlen komponens marad, amely a teljes gráfot lefedi.
Boruvka(G):
Inicializáld a komponenst minden csúcsra (kezdetben önálló csúcsok)
MST = üres halmaz
amíg a komponensek száma > 1:
minden komponens esetén:
keressük meg a legkisebb súlyú élt, amely egy másik komponenshez vezet
adjuk hozzá az összes kiválasztott élt az MST-hez
egyesítsük azokat a komponenseket, amelyeket az új élek összekötöttek
visszatér MST
from collections import defaultdict
class Graph:
def __init__(self, vertices):
self.V = vertices # Csúcsok száma
self.edges = # Gráf élei (forrás, cél, súly)
def add_edge(self, u, v, w):
self.edges.append((u, v, w))
def find_component(self, parent, i):
if parent == i:
return i
return self.find_component(parent, parent)
def union(self, parent, rank, x, y):
xroot = self.find_component(parent, x)
yroot = self.find_component(parent, y)
if rank < rank:
parent = yroot
elif rank > rank:
parent = xroot
else:
parent = xroot
rank += 1
def boruvka(self):
parent =
rank =
mst_weight = 0
mst_edges =
for node in range(self.V):
parent.append(node)
rank.append(0)
num_components = self.V
while num_components > 1:
cheapest = * self.V
for u, v, w in self.edges:
uroot = self.find_component(parent, u)
vroot = self.find_component(parent, v)
if uroot != vroot:
if cheapest == -1 or cheapest > w:
cheapest = (u, v, w)
if cheapest == -1 or cheapest > w:
cheapest = (u, v, w)
for node in range(self.V):
if cheapest != -1:
u, v, w = cheapest
uroot = self.find_component(parent, u)
vroot = self.find_component(parent, v)
if uroot != vroot:
self.union(parent, rank, uroot, vroot)
mst_weight += w
mst_edges.append((u, v, w))
num_components -= 1
return mst_weight, mst_edges
# Példa gráf
g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)
mst_weight, mst_edges = g.boruvka()
print("Minimális feszítőfa súlya:", mst_weight)
print("MST élei:", mst_edges)
#include <iostream>
#include <vector>
#include <tuple>
#include <limits>
using namespace std;
struct Edge {
int src, dest, weight;
};
struct Graph {
int V, E;
vector<Edge> edges;
Graph(int V, int E) : V(V), E(E) {}
void addEdge(int src, int dest, int weight) {
edges.push_back({src, dest, weight});
}
int find(int parent, int i) {
if (parent == i)
return i;
return find(parent, parent);
}
void unionSets(int parent, int rank, int x, int y) {
int xroot = find(parent, x);
int yroot = find(parent, y);
if (rank < rank) {
parent = yroot;
} else if (rank > rank) {
parent = xroot;
} else {
parent = xroot;
rank++;
}
}
void boruvka() {
vector<Edge> mst;
int parent, rank;
for (int i = 0; i < V; i++) {
parent = i;
rank = 0;
}
int numComponents = V, mstWeight = 0;
while (numComponents > 1) {
vector<Edge> cheapest(V, {-1, -1, numeric_limits<int>::max()});
for (auto& edge : edges) {
int u = find(parent, edge.src);
int v = find(parent, edge.dest);
if (u != v) {
if (edge.weight < cheapest.weight)
cheapest = edge;
if (edge.weight < cheapest.weight)
cheapest = edge;
}
}
for (int i = 0; i < V; i++) {
if (cheapest.weight != numeric_limits<int>::max()) {
int u = cheapest.src;
int v = cheapest.dest;
int setU = find(parent, u);
int setV = find(parent, v);
if (setU != setV) {
mst.push_back(cheapest);
mstWeight += cheapest.weight;
unionSets(parent, rank, setU, setV);
numComponents--;
}
}
}
}
cout << "Minimális feszítőfa súlya: " << mstWeight << endl;
cout << "MST élei:" << endl;
for (auto& edge : mst) {
cout << edge.src << " - " << edge.dest << " (" << edge.weight << ")" << endl;
}
}
};
int main() {
Graph g(4, 5);
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.boruvka();
return 0;
}
A Borůvka-algoritmus hatékonyan alkalmazható minimális feszítőfák kialakítására, különösen párhuzamos számítási környezetekben. Bár más algoritmusok, például a Kruskal- és a Prim-algoritmus gyakrabban használtak, a Borůvka-algoritmus egyszerűsége miatt különösen hasznos nagy gráfokon.