Borůvka-algoritmus
Kiejtés
- IPA: [ ˈborůfkɒɒlɡoritmuʃ] érvénytelen IPA-karakterek (ů)
Főnév
- (matematika, gráfelmélet, algoritmusok) A Borůvka-algoritmus egy mohó algoritmus mely alkalmas egy minimális feszítőfa megkeresésére egy olyan gráfban, amelyben az összes él különbözik, vagy egy minimális feszítőerdő megtalálására olyan gráf esetén, amely nem kapcsolódik.
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.
Alapötlet
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.
Tulajdonságok
- Időkomplexitás: (O(E V)), ahol (E) az élek száma és (V) a csúcsok száma.
- Hatékonyság: Könnyen párhuzamosítható, mivel minden komponens önállóan választja ki a legkisebb élt.
- Súlyozott, összefüggő gráfokra alkalmazható.
Pszeudokód
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
Python implementáció
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] == i:
return i
return self.find_component(parent, parent[i])
def union(self, parent, rank, x, y):
xroot = self.find_component(parent, x)
yroot = self.find_component(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 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 = [-1] * 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[uroot] == -1 or cheapest[uroot][2] > w:
cheapest[uroot] = (u, v, w)
if cheapest[vroot] == -1 or cheapest[vroot][2] > w:
cheapest[vroot] = (u, v, w)
for node in range(self.V):
if cheapest[node] != -1:
u, v, w = cheapest[node]
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)
C++ implementáció
#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] == i)
return i;
return find(parent, parent[i]);
}
void unionSets(int parent[], int rank[], int x, int y) {
int xroot = find(parent, x);
int yroot = find(parent, y);
if (rank[xroot] < rank[yroot]) {
parent[xroot] = yroot;
} else if (rank[xroot] > rank[yroot]) {
parent[yroot] = xroot;
} else {
parent[yroot] = xroot;
rank[xroot]++;
}
}
void boruvka() {
vector<Edge> mst;
int parent[V], rank[V];
for (int i = 0; i < V; i++) {
parent[i] = i;
rank[i] = 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[u].weight)
cheapest[u] = edge;
if (edge.weight < cheapest[v].weight)
cheapest[v] = edge;
}
}
for (int i = 0; i < V; i++) {
if (cheapest[i].weight != numeric_limits<int>::max()) {
int u = cheapest[i].src;
int v = cheapest[i].dest;
int setU = find(parent, u);
int setV = find(parent, v);
if (setU != setV) {
mst.push_back(cheapest[i]);
mstWeight += cheapest[i].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;
}
Összegzés
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.
- Borůvka-algoritmus - Értelmező szótár (MEK)
- Borůvka-algoritmus - Etimológiai szótár (UMIL)
- Borůvka-algoritmus - Szótár.net (hu-hu)
- Borůvka-algoritmus - DeepL (hu-de)
- Borůvka-algoritmus - Яндекс (hu-ru)
- Borůvka-algoritmus - Google (hu-en)
- Borůvka-algoritmus - Helyesírási szótár (MTA)
- Borůvka-algoritmus - Wikidata
- Borůvka-algoritmus - Wikipédia (magyar)