primMST<T> function

List<WeightedEdge<T>> primMST<T>(Map<T, List<WeightedEdge<T>>> graph)

Implementation

List<WeightedEdge<T>> primMST<T>(Map<T, List<WeightedEdge<T>>> graph) {
  final Set<T> allNodes = {...graph.keys};
  for (final edges in graph.values) {
    for (final e in edges) {
      allNodes.add(e.source);
      allNodes.add(e.target);
    }
  }

  final Set<T> visited = <T>{};
  final List<WeightedEdge<T>> mst = [];

  // This function processes one connected component of the graph
  void processComponent(T start) {
    visited.add(start);

    // Use the Min-Heap as our frontier instead of a List
    // It will automatically keep the lowest-weight edge at the top
    final frontier = _MinHeap<WeightedEdge<T>>(
      (a, b) => a.weight.compareTo(b.weight),
    );
    (graph[start] ?? <WeightedEdge<T>>[]).forEach(frontier.add);

    while (frontier.isNotEmpty) {
      // No more sorting! Just get the minimum element efficiently.
      final edge = frontier.removeMin();

      final T v = visited.contains(edge.source) ? edge.target : edge.source;
      if (visited.contains(v)) continue;

      visited.add(v);
      mst.add(edge);

      for (final e in graph[v] ?? <WeightedEdge<T>>[]) {
        final T next = visited.contains(e.source) ? e.target : e.source;
        if (!visited.contains(next)) frontier.add(e);
      }
    }
  }

  // Process all components to handle disconnected graphs (forests)
  for (final n in allNodes) {
    if (!visited.contains(n)) {
      processComponent(n);
    }
  }
  return mst;
}