算法 - 图（Graph）- 生成树（Spanning Tree）- Prim算法

• 图（Graph）

• 图（Graph）- 生成树（Spanning Tree）

• 图（Graph）- 生成树（Spanning Tree）- Kruskal算法

切分定理

• 切分（Cut）：把图中的节点分为两部分，成为一个切分
• 下图有个切分C = (S, T)，S = {A, B, D}，T = {C, E}
  
• 横切边（Crossing Edge）：如果一个边的两个顶点，分别属于切分的两部分，这个边称为横切边
  比如上图的边BC、BE、DE就是横切边
• 切分定理：给定任意切分，横切边中权值最小的边必然属于最小生成树

Prim算法 - 执行过程

• 假设G = (V, E)是有权的连通图（无向），A是G中最小生成树的边集
• 算法从S = { u } (u ∈V)，A = {} 开始，重复执行下述操作，知道S = V为止
  找到切分C = (S, V - S) 的最小横切边(u, v)并入集合A，同时将v并入集合S
  
  
  

Prim算法 - 实现

private Set<EdgeInfo<V, E>> prim() {
    Iterator<Vertex<V, E>> it = vertices.values().iterator();
    if (!it.hsaNext()) return null;
    Vertex<V, E> vertex = it.next();
    Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
    Set<Vertex<V, E>> addedVertices = new HashSet<>();
    addedVertices.add(vertex);
    MinHeap<Edge<V, E>> heap = new MinHeap<>(Vertex.outEdges, edgeComparator);
    int verticesSize = vertices.size();
    while (!heap.isEmpty() && addedVertices.size() < verticesSize) {
        Edge<V, E> edge = heap.remove();
        if (addedVertices.contains(edge.to)) continue;
        edgeInfos.add(edge.info());
        addedVertices.add(edge.to);
        heap.addAll(edge.to.outEdges);
    }
    return edgeInfos;
}