最小生成树 Prim算法 java_prim算法java求解最小生成树

边的实现，同时表示了两个顶点和权重，个人理解 Prim 算法是不断的找最小的横切边，因此边使用这样的表示方便我们获得边的信息

/**
	边的构建
*/
class Edge implements Comparable<Edge> {
    int v;
    int w;
    double weight;

    public Edge(int v, int w, double weight) {
        this.v = v;
        this.w = w;
        this.weight = weight;
    }

    // 返回边的其中一个顶点
    int either() {
        return v;
    }

    // 返回与v不同的另一个顶点
    int other(int v) {
        if (v == this.w) {
            return this.v;
        }
        return this.w;
    }

    @Override
    public int compareTo(Edge o) {
        return Double.compare(this.weight, o.weight);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

加权无向图的实现

/**
 * 加权无向图的实现
 */
class EdgeWeightedGraph {
    int v;
    ArrayList[] adj;

    public EdgeWeightedGraph(int v) {
        this.v = v;
        adj = new ArrayList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new ArrayList();
        }
    }

    void addEdge(int v, int w, double weight) {
        Edge e = new Edge(v, w, weight);
        adj[v].add(e);
        adj[w].add(e);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

切分定理：将图的顶点分成两个集合，横切边中权重最小的那条边一定在最小生成树中，（假设图的最小生成树是 T，横切边中最小的边是 e 且 e 不在 T 中，如果将 e 添加进最小生成树中 T 中，那么就会形成一个包含边 e 在内的环，此时可以删除环中在最小生成树中的另一条边 f，就可以得到一个权重更小的最小生成树 T 了，因此 e 一定在 最小生成树中 ）。
其实就是维护两个（在和不在最小生成树的顶点的）集合，每次都从两个集合的横切边中取出最小的边加到最小生成树中，当最小生成树加入新的边后，原来的横切边有些就失效了，并且还有了新的横切边。

/**
 * @author wangshaoyu
 * Prim 算法的延时实现的特点就是失效的边依然在最小堆中，但是我们可以通过判断该边的两个顶点是否在最小生成树中来判断该边是否已经失效
 */
public class LazyPrim {

    boolean[] marked;         // 标记这个顶点是否已经在最小生成树中，初始化为 false
    PriorityQueue<Edge> pq;   // 用一个最小堆存放所有横切边
    ArrayDeque<Edge> queue;   // 存放最小生成树里的边

    public LazyPrim(EdgeWeightedGraph G) {
        marked = new boolean[G.v];
        pq = new PriorityQueue<>();
        queue = new ArrayDeque<>();

        visit(G, 0); // 先把第 0 个顶点加到最小生成树中，并把该顶点的邻接边加到最小堆中

        while (! pq.isEmpty()) {
            Edge e = pq.poll();
            int v = e.either();
            int w = e.other(v);
            // 这条边的两个顶点都在最小生成树中，说明这条边已经失效了
            if (marked[v] == true && marked[w] == true) {
                continue; // 最小生成树构建完成后，最小堆里面的边都是失效的，然后就一直continue直到最小堆为空
            }
            // 加入最小生成树的这条边的marked会有一个顶点是true，一个是false
            queue.add(e);
            // 继续将新出现的横切边加进最小堆里
            if (marked[v] == false) {
                visit(G, v);
            }
            if (marked[w] == false) {
                visit(G, w);
            }
        }
    }
    
    // 将 v 标记为true 表示将这个结点加入到最小生成树中，然后将与 v 相连的点（不在最小生成树中的）的边添加进堆中
    void visit(EdgeWeightedGraph G, int v) {
        marked[v] = true;
        for (Object o : G.adj[v]) {
            Edge e = (Edge) o;
            if (marked[e.other(v)] == false) {
                pq.offer(e);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48