图论13-最小生成树-Kruskal算法+Prim算法

1 最小生成树

2 最小生成树Kruskal算法的实现

2.1 算法思想

1. 基本思想：按照权值从小到大的顺序选择 n-1 条边，并保证这 n-1 条边不构成回路
2. 具体做法：首先构造一个只含 n 个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。

2.2 算法实现

2.2.1 如果图不联通，直接返回空，该图没有mst

 CC cc = new CC(G);if(cc.count() > 1) return;

2.2.2 获得图中的所有边，并且进行排序

ArrayList<WeightedEdge> edges = new ArrayList<>();for(int v = 0; v < G.V(); v ++)for(int w: G.adj(v))if(v < w) // 剪枝：0-2,2-0，只判断0-2，避免重复edges.add(new WeightedEdge(v, w, G.getWeight(v, w)));Collections.sort(edges);

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

public int compareTo(WeightedEdge another){return weight - another.weight;
}

2.2.3 取边进行判断是否形成环

2.2.3.1判断是否形成环

通过并查集标记联通分量。

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

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

UF uf = new UF(G.V());
for(WeightedEdge edge: edges){int v = edge.getV();int w = edge.getW();// 判断选择的边的两个顶点是否属相连if(!uf.isConnected(v, w)){ mst.add(edge);uf.unionElements(v, w); // 合并两个顶点和边}
}

3 最小生成树Prim算法的实现

3.1 算法思想

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

将顶点分为两类，一类是在查找的过程中已经包含在树中的（假设为 B 类），剩下的是另一类（假设为 A 类）。

3.2 算法实现

3.2.1 如果图不联通，直接返回空，该图没有mst

 CC cc = new CC(G);if(cc.count() > 1) return;

3.2.2 使用visited数组区分A组B组

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

boolean visited[] = new boolean[G.V()];
visited[0] = true;

3.2.3 添加边生成mst

声明一个变量minEdge用于标记权重最小的边。

for(int i = 1; i < G.V(); i ++){WeightedEdge minEdge = new WeightedEdge(-1, -1, Integer.MAX_VALUE);for(int v = 0; v < G.V(); v ++)if(visited[v]) //当前组的节点进行遍历for(int w: G.adj(v)) //找到相邻的顶点// 如果当前的顶点跟上一个顶点不是一个组// 并且权重比minEdge标记的权重更小if(!visited[w] && G.getWeight(v, w) < minEdge.getWeight())// 更新minEdge的值，并加入到mst中minEdge = new WeightedEdge(v, w, G.getWeight(v, w));mst.add(minEdge);visited[minEdge.getV()] = true;visited[minEdge.getW()] = true;
}

3.2.4 切分优化 - （一定要掌握）

使用优先队列取最短的边。

拓展的过程中，优先队列的边不一定是合法的边。

在构建mst时进行判断边的合法性。

 Queue pq = new PriorityQueue<WeightedEdge>();// 初始化for(int w: G.adj(0))pq.add(new WeightedEdge(0, w, G.getWeight(0, w)));// 循环取边while(!pq.isEmpty()){WeightedEdge minEdge = (WeightedEdge) pq.remove();// 判断边的合法性if(visited[minEdge.getV()] && visited[minEdge.getW()])continue; //  继续循环取边mst.add(minEdge);int newv = visited[minEdge.getV()] ? minEdge.getW() : minEdge.getV(); // 找到新边不属于同一集合的点visited[newv] = true; //设置为同一集合// 更新横切边的优先队列for(int w: G.adj(newv))if(!visited[w])pq.add(new WeightedEdge(newv, w, G.getWeight(newv, w)));}