三否网站,wordpress 在线教学,网站做支付借口多少钱,做视频哪个网站素材好文章目录 1 最小生成树2 最小生成树Kruskal算法的实现2.1 算法思想2.2 算法实现2.2.1 如果图不联通#xff0c;直接返回空#xff0c;该图没有mst2.2.2 获得图中的所有边#xff0c;并且进行排序2.2.2.1 Edge类要实现Comparable接口#xff0c;并重写compareTo方法 2.2.3 取… 文章目录 1 最小生成树2 最小生成树Kruskal算法的实现2.1 算法思想2.2 算法实现2.2.1 如果图不联通直接返回空该图没有mst2.2.2 获得图中的所有边并且进行排序2.2.2.1 Edge类要实现Comparable接口并重写compareTo方法 2.2.3 取边进行判断是否形成环2.2.3.1判断是否形成环 3 最小生成树Prim算法的实现3.1 算法思想3.2 算法实现3.2.1 如果图不联通直接返回空该图没有mst3.2.2 使用visited数组区分A组B组3.2.3 添加边生成mst3.2.4 切分优化 - 一定要掌握 1 最小生成树 2 最小生成树Kruskal算法的实现
2.1 算法思想
基本思想按照权值从小到大的顺序选择 n-1 条边并保证这 n-1 条边不构成回路具体做法首先构造一个只含 n 个顶点的森林然后依权值从小到大从连通网中选择边加入到森林中并使森林中不产生回路直至森林变成一棵树为止。 2.2 算法实现
2.2.1 如果图不联通直接返回空该图没有mst CC cc new CC(G);if(cc.count() 1) return;2.2.2 获得图中的所有边并且进行排序
ArrayListWeightedEdge 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 PriorityQueueWeightedEdge();// 初始化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)));}
