Borůvka
What is Borůvka?
Borůvka is the oldest algorithm solving MST, which is based on the greedy algorithm.
How does it work?
Borůvka considers each node as a component initially, and expand the component to contain more nodes gradually until the numbers of component equal to 1. It follows the greedy algorithm, choosing the best out-edge to expand every time. The process of expanding is same as the union function of DSU. We suppose that the best out-edge ID of every component is -1 initially, and update the best out-edge of each component by comparing the weight of each out-edge.
We need the start node and the end node of an edge, checking whether they are in the same component(find their root) or not. After that, if the ID component’s best out-edge is -1, which means it haven’t scanned its out-edge, we add the out-edge scanned firstly; if it is not -1, which means it have contain an best out-edge ID of the scanned, we compare the weight of the best one and the new one to choose the new best. After we update all edges, we need to merge the component. We traverse the best out-edge of all nodes, and merge the components the best out-edge connected. Repreat the whole process until the number of components equal to 1.
Inplement in c++ code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
struct Edge{
int u, v, w;
Edge(int start, int endm int weight) : u(start), v(end), w(weight) {}
};
struct DSU{
vector<int> parent, size;
DSU(int n) : parent(n), size(n, 1){
for(int i = 0; i < n; ++i) parent[i] = i;
}
int find(int x)
{
if(x != parent[x]) parent[x] = find(parent[x]);
return parent[x];
}
bool union(int a, int b)
{
int pa = find(a); int pb = find(b);
if(pa == pb) return false;
if(size[pa] < size[pb]) swap(pa, pb);
parent[pb] = pa;
size[pa] += size[pb];
return true;
}
};
int Borůvka(int n, vector<Edge> edges)
{
DSU dsu(n);
int total = 0; int componentNum = n;
while(componentNum > 1)
{
vector<int> bestOutEdgeOf(n, -1);
for(int i = 0; i < edges.size(); ++i)
{
int u = dsu.find(edges[i].u);
int v = dsu.find(edges[i].v);
if(u == v) continue;
if(bestOutEdgeOf[u] == -1 || edges[i].w < edges[bestOutEdgeOf[u]].w) bestOutEdgeOf[u] = i;
if(bestOutEdgeOf[v] == -1 || edges[v].w < edges[bestOutEdgeOf[v]].w) bestOutEdgeOf[v] = i;
}
for(int i = 0; i < n; ++i)
{
int outEdge = bestOutEdgeOf[i];
if(outEdge != -1)
{
Edge e = edges[outEdge];
if(dsu.union(e.u, e.v))
{
component--;
total += e.w;
}
}
}
}
}