最小生成树问题的两种算法 |
您所在的位置：网站首页 › kruskal算法求最小生成树步骤 › 最小生成树问题的两种算法 |
最小生成树问题的两种算法
|
最小生成树
摘要最小生成树的定义Prim算法Kruskal
超级详细的基础算法和数据结构合集： https://blog.csdn.net/GD_ONE/article/details/104061907 摘要本文主要介绍最小生成树以及求最小生成树常用的两种算法，Prim算法和Kruskal算法。 最小生成树的定义最小生成树是一个图的总边权最小的极小连通子图 Prim算法Prim算法和Dijkstra算法实现方式十分相似： Dijkstra是先设定一个点集，初始时点集为空，每次找出一个距离起点最近的点，将该点加入集合，然后短缩其该点的邻接点到顶点的距离。。 Prim是先设定一个边集，初始时边集为空，每次从待查找的边中找出一个与边集中的点相连的最短边，然后将该边加入边集，然后将该边的邻接边的状态更新为待查找。 另：Prim适用于稠密图 图示： 初始时所有边都未加入边集：
第一次循环只能更新1号点和其邻接点的距离，此时还没有一条边加入最小生成树，接下来每循环1次，能得到一个最短边，所以要循环n次。 先看下代码： public static int Prim(){ Arrays.fill(dis, 0x3f3f3f3f); //设所有边距离边集的的距离为正无穷，也就是设所有边的状态为不可查找 int res = 0;// 存储最小生成树的总边权 dis[1] = 0; // 设1号点距离边集的距离为0 for(int i = 0; i if(st[j] == 0 && minv > dis[j]){ t = j; minv = dis[j]; } } if(minv == INF) return INF;// 最短边是无穷大，说明该图不连通 res += dis[t]; st[t] = 1; //将t的邻接边的状态更新为待查找 for(int j = 1; j static BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); static final int N = 1005, INF = 0x3f3f3f3f; static int[][] g = new int[N][N];// 邻接矩阵 static int n, m; static int[] dis = new int[N]; static int[] st = new int[N]; public static int Prim(){ Arrays.fill(dis, 0x3f3f3f3f); int res = 0; dis[1] = 0; for(int i = 0; i if(st[j] == 0 && minv > dis[j]){ t = j; minv = dis[j]; } } if(minv == INF) return INF; res += dis[t]; st[t] = 1; for(int j = 1; j String[] s = in.readLine().split(" "); n = Integer.parseInt(s[0]); m = Integer.parseInt(s[1]); for(int i = 1; i int a, b, w; String[] s1 = in.readLine().split(" "); a = Integer.parseInt(s1[0]); b = Integer.parseInt(s1[1]); w = Integer.parseInt(s1[2]); g[a][b] = g[b][a] = Math.min(g[a][b], w); } int res = Prim(); if(res == INF) out.write("impossible\n"); else out.write(res+"\n"); out.flush(); } }另：Prim和Dijkstra一样都可以使用优先队列优化，但是写着比较麻烦，而Kruskal实现简单，效率又高，所以处理稀疏图就用Kruskal了，本文不在介绍堆优化版Prim。 KruskalKruskal适用于稀疏图的原因是，该算法是将所有边按升序排序，然后依次将未加入最小生成树最小的边加入最小生成树。 为什么这样就可以得到一个图的最小生成树了呢？ 反证法： 当前最小边连接了两个连通块， 一个是最小生成树所在的连通块，一个是未加入最小生成树，但最终仍要加入其中的连通块。 如图： Kruskal算法实现起来就简单多了，第一步排序，第二步检查当前最小边所连接的两个点是否都在最小生成树的点集内，不在的话就将其加入最小生成树。 这里用并查集来判断两点是否在同一集合内。 不知道并查集的请点击：并查集 public static int find(int x){ // 很经典的并查集查找函数，此函数还实现了路径压缩 if(p[x] != x) p[x] = find(p[x]); return p[x]; } public static int kruskal1()throws IOException{ Arrays.sort(g, 0, m); // 对边集排序，g数组存储所有边 int cnt = 0, res = 0;// cnt表示加入最小生成树的有几条边 // res表示最小生成树的边权 for(int i = 1; i // 如果a和b不在同一个集合，将a和b合并，将边(a,b)加入最小生成树 p[a] = b; cnt ++; res += t.w; } } if(cnt != n - 1) return 0x3f3f3f3f;//如果少于n-1条则该图不连通，无最小生成树 else return res; }习题： Kruskal算法求最小生成树 代码： import java.io.*; import java.util.*; public class Main{ static BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); public static class pair implements Comparable{ int a, b, w; pair(int u, int v, int x){ a = u; b = v; w = x; } public int compareTo(pair p) { // 自定义类需要重写比较器 return this.w - p.w; } } static final int N = 200010, INF = 0x3f3f3f3f; static int n, m; static int[] p = new int[N]; static pair[] g = new pair[N]; public static int Int(String s){ return Integer.parseInt(s); } public static int find(int x){ if(p[x] != x) p[x] = find(p[x]); return p[x]; } public static int kruskal1()throws IOException{ Arrays.sort(g, 0, m-1); int cnt = 0, res = 0; for(int i = 1; i p[a] = b; cnt ++; res += t.w; } } if(cnt != n - 1) return 0x3f3f3f3f; else return res; } public static void main(String[] args) throws IOException{ String[] s = in.readLine().split(" "); n = Int(s[0]); m = Int(s[1]); for(int i = 0, j = 0; i |
从一号点开始，将其邻接点的状态设为待查找：
然后找出待查找的边中的最短边并将其邻接边的状态设为待查找：
重复以上两步： 
所有点都被加入最小生成树，算法结束，最小生成树为： 
接下来就是代码实现了 对于实现Prim算法，需要两个数组， 一个标记该点是否在边集内，一个存储该点到边集的距离(也就是标记状态的数组)，还需要一个整型变量存储最小生成树的总边权。
看到上图发绿光的边了吗： 如果不将（1,2）加入最小生成树，最小生成树所在的连通块最终仍然要通过其他边连接点（2,4,5）所连接的连通块，而其他边的权值一定大于(1,2),这样总边权就增大了，就不是最小生成树了。 代码实现：【本文地址】
今日新闻 |
推荐新闻 |