Skip to content

Instantly share code, notes, and snippets.

@ellemenno
Last active April 15, 2022 14:43
Show Gist options
  • Save ellemenno/b6c35aa7589ee2d90c71d658d9a4d254 to your computer and use it in GitHub Desktop.
Save ellemenno/b6c35aa7589ee2d90c71d658d9a4d254 to your computer and use it in GitHub Desktop.
minimum spanning tree in dart using kruskall's algorithm and disjoint set union
/// Represents a weighted graph edge, connecting vertices [v1] and [v2].
class Edge {
final int v1, v2;
int weight;
@override
String toString() => '${v1},${v2};${weight}';
Edge(this.v1, this.v2, this.weight);
}
/// Computes a Minimum Spanning Tree for an undirected edge-weighted graph, given a list of edges and count of vertices.
///
/// When edge weights are not unique, the [result] is one of potentially multiple solutions.
///
/// Uses [Kruskall's algortihm](https://en.wikipedia.org/wiki/Kruskal%27s_algorithm) with [Disjoint Set Union](https://en.wikipedia.org/wiki/Disjoint-set_data_structure).
///
/// Adapted to Dart from https://cp-algorithms.com/graph/mst_kruskal_with_dsu.html
class MST {
static int _findSet(int v, List<int> parent) {
// follow chain of parents from given vertex v up to root of set
// root represents set to which v belongs and may be v itself
// path compression: every vertex visited on way to root is part of same set,
// so improve execution time by updating parents to point closer to root
while(parent[v] != v) {
parent[v] = parent[parent[v]];
v = parent[v];
}
return v;
}
static void _zero(List<int> list) {
final int n = list.length;
for (int i = 0; i < n; i++) {
list[i] = 0;
}
}
late final int _numVerts;
late final List<int> _parent, _rank;
late final List<Edge> _edges;
List<Edge> result = [];
int cost = 0;
void _makeSet(int v) {
// adds vertex v into a new set containing only itself (as root), and initializes rank
_parent[v] = v;
_rank[v] = 0;
}
void _init() {
// prepare for compute
_zero(_parent);
_zero(_rank);
result.clear();
cost = 0;
for (int i = 0; i < _numVerts; i++) {
_makeSet(i);
}
_edges.sort((a, b) => a.weight.compareTo(b.weight));
}
/// Compute the minimum spanning tree, storing participating edges in [result].
void compute() {
_init();
int a, b, c;
for (Edge e in _edges) {
a = _findSet(e.v1, _parent);
b = _findSet(e.v2, _parent);
// if a and b have different roots (not a cycle), then edge belongs in result
if (a != b) {
cost += e.weight;
result.add(e);
// unionSets
// replace set containing a and set containing b with their union
// use rank to minimize tree height by keeping smaller trees within larger ones
if (_rank[a] < _rank[b]) {
// swap so a is always higher rank
c = a;
a = b;
b = c;
}
_parent[b] = a;
if (_rank[a] == _rank[b]) {
_rank[a]++;
}
}
}
}
/// Negate the weights of every edge.
///
/// Can be used to find a maximum spanning tree by letting [compute] find the 'most negative' weights.
void invertWeights() {
for (Edge e in _edges) {
e.weight *= -1;
}
}
/// Prepare a data structure to compute the minimum spanning tree given a count of vertices and a list of edges.
///
/// Use [compute] to find the tree, and access it from [result].
/// Find a maximum spanning tree by calling [invertWeights] before [compute].
MST(this._numVerts, this._edges) {
_parent = List<int>.filled(_numVerts, 0, growable: false);
_rank = List<int>.filled(_numVerts, 0, growable: false);
}
}
void main() {
/*
5
(3)---(2) 6 vertices 9 edges: v1,v2;weight
9/ | \ | \8
(4) |1 \3 |3 (5) 0 3 0,1;2 1,2;3 2,3;5
4\ | \ | /7 1 4 0,3;1 1,3;3 2,5;8
(0)---(1) 2 5 0,4;4 1,5;7 3,4;9
2
*/
List<Edge> edges = [
Edge(0, 1, 2),
Edge(0, 3, 1),
Edge(0, 4, 4),
Edge(1, 2, 3),
Edge(1, 3, 3),
Edge(1, 5, 7),
Edge(2, 3, 5),
Edge(2, 5, 8),
Edge(3, 4, 9)
];
print('regular - minimum');
MST m = MST(6, edges);
m.compute();
print(m.result);
print('cost: ${m.cost}');
/*
(3) (2)
| |
(4) |1 |3 (5)
4\ | | /7
(0)---(1)
2
[0,3;1, 0,1;2, 1,2;3, 0,4;4, 1,5;7]
cost: 17
*/
print('inverted - maximum');
m.invertWeights();
m.compute();
print(m.result);
print('cost: ${m.cost}');
/*
5
(3)---(2)
9/ \8
(4) (5)
4\ /7
(0) (1)
[3,4;-9, 2,5;-8, 1,5;-7, 2,3;-5, 0,4;-4]
cost: -33
*/
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment