算法思想2.2

Edge类要实现Comparable接口并重写compareTo方法

2.2.3

个顶点的森林然后依权值从小到大从连通网中选择边加入到森林中并使森林中不产生回路直至森林变成一棵树为止。

2.2

剪枝0-2,2-0只判断0-2避免重复edges.add(new

WeightedEdge(v,

w)));Collections.sort(edges);2.2.2.1

Edge类要实现Comparable接口并重写compareTo方法

public

如果添加进来的边的两个顶点属于相同的集合那么说明一定会形成环。

new

判断选择的边的两个顶点是否属相连if(!uf.isConnected(v,

w)){

mst.add(edge);uf.unionElements(v,

w);

Prim的核心思想就是使用贪心算法每次从连通图中找到一条符合条件的权值最小的边重复这样的操作N-1次选出的N-1条权值最小的边组成的树就是最下生成树。

3.2

初始化的时候visited数组起始的元素为true其余全部设置为galse表示两个不同的组

boolean

并且权重比minEdge标记的权重更小if(!visited[w]

G.getWeight(v,

w));mst.add(minEdge);visited[minEdge.getV()]

true;

循环取边while(!pq.isEmpty()){WeightedEdge

minEdge

判断边的合法性if(visited[minEdge.getV()]

visited[minEdge.getW()])continue;

newv

G.adj(newv))if(!visited[w])pq.add(new

WeightedEdge(newv,