最小生成树 Prim

最小生成树是无向图

1. 可以从任意节点出发来寻找最小生成树
2. 某个点加入到被选取的点中后，解锁这个点出发的所有新的边
3. 在所有解锁的边中选最小的边，然后看看这个边会不会形成环
4. 如果会，不要当前边，继续考察剩下解锁的边中最小的边，重复 3
5. 如果不会，要当前边，将该边的指向点加入到被选取的点中，重复 2
6. 当所有点都被选取，最小生成树就得到了

public static Set<Edge> primMST(Graph graph) {
  // 解锁的边进入小根堆
  PriorityQueue<Edge> priorityQueue = new PriorityQueue<>((o1, o2) -> {
    return o1.weight - o2.weight;
  });

  HashSet<Node> nodeSet = new HashSet<>();
  Set<Edge> result = new HashSet<>(); // 依次挑选的边在Result里
  for (Node node : graph.nodes.values()) {
    // Node 是开始点
    if (!nodeSet.contains(node)) {
      nodeSet.add(node);
      for (Edge edge : node.edges)
        priorityQueue.add(edge); // 由一个点，解锁所有相连的边；

      while (!priorityQueue.isEmpty()) {
        Edge edge = priorityQueue.poll(); // 弹出解锁的边中，最小的边
        Node toNode = edge.to;// 可能是一个新的点
        if (!nodeSet.contains(toNode)) {
          // 不含有的时候，就是新的点
          nodeSet.add(toNode);
          result.add(edge);
          for (Edge nextEdge : toNode.edges)
            priorityQueue.add(nextEdge);
        }
      }
    }
  }
  return result;
}