kruskalMST<T> function

List<WeightedEdge<T>> kruskalMST<T>(
  1. Set<T> nodes,
  2. List<WeightedEdge<T>> edges
)

Implementation

List<WeightedEdge<T>> kruskalMST<T>(Set<T> nodes, List<WeightedEdge<T>> edges) {
  final DisjointSet<T> ds = DisjointSet<T>();
  for (final n in nodes) {
    ds.add(n);
  }

  edges.sort((a, b) => a.weight.compareTo(b.weight));

  final List<WeightedEdge<T>> result = [];
  for (final e in edges) {
    if (ds.find(e.source) != ds.find(e.target)) {
      ds.union(e.source, e.target);
      result.add(e);
    }
  }
  return result;
}